1로 만들기 2 (feat. 백준, 12852번)

1로 만들기 2
https://www.acmicpc.net/problem/12852

12852번: 1로 만들기 2

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
using namespace std;
int dp[1000001];
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N;
	cin >> N;
	for (register int i = 0; i <= N; ++i)
		dp[i] = i;
	dp[1] = 0;
	for (register int i = 2; i <= N; ++i) {
		if (i % 2 == 0)
			dp[i] = min(dp[i], dp[i / 2]);
		if (i % 3 == 0)
			dp[i] = min(dp[i], dp[i / 3]);
		dp[i] = min(dp[i], dp[i - 1]) + 1;
	}
	cout << dp[N] << "\n";
	while (N > 0) {
		cout << N << " ";
		if (N % 2 == 0 && dp[N / 2] == dp[N] - 1)
			N /= 2;
		else if (N % 3 == 0 && dp[N / 3] == dp[N] - 1)
			N /= 3;
		else
			N -= 1;
	}
	return 0;
}
// *&)*@*

1. 전형적인 dp 문제입니다.
2. dp의 인덱스는 1을 만들기 위한 연산의 개수입니다.
3. dp의 현재 인덱스는 /2 /3 -1 중 가장 작은 값 (가장 작은 연산을 사용하는 경우) 에서 +1이 됩니다. (한번 더 연산이 들어가기 때문입니다.)
4. 완성된 dp[N]은 1을 만들기 위한 총 연산의 최소 횟수가 입력됩니다.
5. 또한 완성된 dp[N]은 /2 /3 -1 을 역으로 추적하면 N -> 1로의 과정을 알 수 있습니다.