[백준/C++] 12852 1로 만들기 2

https://www.acmicpc.net/problem/12852

코드

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> dp(1000001, 1000001);
	vector<int> parent(1000001);

	dp[1] = 0, dp[2] = 1, dp[3] = 1;

	parent[1] = 0,  parent[2] = 1, parent[3] = 1;

	for (int i = 4; i <= n; i++) {
		if (i % 3 == 0 && dp[i/3]+ 1 < dp[i]) {
			dp[i] = dp[i / 3] + 1;
			parent[i] = i / 3;
		}
		if (i % 2 == 0 && dp[i / 2] + 1 < dp[i]) {
			dp[i] = dp[i / 2] + 1;
			parent[i] = i / 2;
		}
		if (dp[i - 1] + 1 < dp[i]) {
			dp[i] = dp[i - 1] + 1;
			parent[i] = i - 1;
		}
	}
	cout << dp[n] << "\n";

	while (n) {
		cout << n << " ";
		n = parent[n];
	}
	return 0;
}

 

설명

기본적인 dp + 경로 추적 문제이다. 이를 위해 dp 점화식을 먼저 세운다.

 

x를 1로 만들기 위해 필요한 연산의 횟수

• x = 1 ➡️ 0
• x = 2 ➡️ 1 (2번이나 3번 연산 이용)
• x = 3 ➡️ 1 (1번 연산 이용)
• x > 3 ➡️ 1~3번 연산을 통해 x에 도달하는데 걸리는 최소 횟수 
  • x % 3 == 0  ➡️ min(dp[x], dp[x/3]+1)
  • x % 2 == 0  ➡️ min(dp[x], dp[x/2]+1)
  • min(dp[x], dp[x-1]+1)

이를 그대로 코드로 구현하면 된다. 이때 경로 추적이 필요하기 때문에 x > 3일 때 최솟값이 갱신될 때마다 parent[x]도 같이 갱신해준다. while문을 돌면서 n = parent[n]으로 n을 갱신해주면서 n을 출력한다. parent[1] = 0으로 설정해서 1까지 출력하면 while문을 탈출한다.

느낀 점

유사한 문제를 많이 풀어봐서 금방 풀었다!