[BOJ] 12852 - 1로 만들기 2

[백준] 12852 - 1로 만들기 2

접근

가장 간단하고 무식한 방법으로 풀 수 있는 방법을 생각해본다.
현재 위치에서 갈 수 있는 모든 선택지를 돌아보면서 BFS를 돌고 1에 도달했을 때 최솟값을 갱신하면 된다(1로 만들기 문제를 이렇게 풀었다)
이것을 반대로 뒤집으면, 1에서 시작해 갈 수 있는 선택지 3개를 현재와 이미 가지고 있던 값 중의 최솟값으로 갱신하면 된다.
1부터 N까지 모든 수를 세가지 선택지에 대해 갱신하는 작업을 거치기 때문에 시간복잡도는 O(3N)으로 넉넉하다!

증명

이게 가능한 이유는 1에서 시작했기 때문에 현재 내가 보는 지점은 반드시 1까지 도달하기 위한 최솟값을 발견했기 때문이다
왜냐하면, 지금은 계산을 뒤집은 것이기 때문에 나보다 작은 수에서 큰수로는 갈 수 있지만 나보다 큰 수에서 작은 수로는 갈 수가 없고, 따라서 현재 가지고 있는 값이 최선이 아닐 경우 작은수부터 확인하는 과정에서 이미 갱신이 끝난 이후여야 하기 때문이다. 모순이 발생하므로 귀류법을 적용해 현재 보고 있는 지점이 가지고 있는 값이 최선의 경우임이 증명된다.

소스코드

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#define INF 987654321
using namespace std;

int dp[1000005], par[1000005];

int main(void) {
	int	n;
	scanf("%d", &n);
	fill(dp, dp + n + 2, INF);
	dp[1] = 0;
	for (int i = 1; i < n; i++) {
		if (dp[i + 1] > dp[i] + 1) {
			dp[i + 1] = min(dp[i + 1], dp[i] + 1);
			par[i + 1] = i;
		}
		if (i * 2 <= n && dp[i * 2] > dp[i] + 1) {
			dp[i * 2] = min(dp[i * 2], dp[i] + 1);
			par[i * 2] = i;
		}
		if (i * 3 <= n && dp[i * 3] > dp[i] + 1) {
			dp[i * 3] = min(dp[i * 3], dp[i] + 1);
			par[i * 3] = i;
		}
	}
	printf("%d\n", dp[n]);
	while (n != 1) {
		printf("%d ", n);
		n = par[n];
	}
	printf("1");
	return 0;
}