[baekjoon 12852] 1로 만들기 2 (DP) (C++)

www.acmicpc.net/problem/12852

12852번: 1로 만들기 2

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

의 조건을 갖고 문제를 푼다.

 

무턱대고 2나 3으로 나뉘어서 나누고 연산을 세주면 안 되고 최솟값을 저장해야 한다.

 

10의 경우로 보면

2로 나뉘어서 10 -> 5 -> 4 -> 2 -> 1 이면 5번이지만

1을 먼저 빼고 시작하면 10 -> 9 -> 3 -> 1으로 4번이다.

 

즉, DP를 통해 최솟값을 갱신해주면서 진행해야 한다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int n, dp[1000001];

int main() {
	cin >> n;

	for (int i = 1; i <= n; i++) {
		dp[i] = i;
	}

	for (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]-1 << "\n";


	while (n != 0) {
		cout << n << " ";
		if (dp[n] == dp[n - 1] + 1) {
			n = n - 1;
		}
		else if (n%2 == 0 && dp[n] == dp[n / 2] + 1) {
			n = n / 2;
		}
		else if (n%3 == 0 && dp[n] == dp[n / 3] + 1) {
			n = n / 3;
		}
	}
}

2나 3으로 나눠지면 현재 값 중 최솟값을 저장해주고 최종적으로 항상 -1을 했을 경우와 비교해준다.

 

또한, 경로를 추적하는 것은 역으로 돌면서 각 연산을 진행했을 때와 현재 값과 1 차이(하나의 연산)가 차이가 나면 그 숫자로 가면 된다.

 

1을 넣으면 0과 1이 출력되어야 한다.