[C++] 백준 1463 : 1로 만들기

 

이번 문제는 정수 N을 입력했을 때 N을 1로 만들기 위해 필요한 최소한의 연산 횟수를 출력하는 문제이다. (N은 1보다 크거나 같다.)

 

문제에서는 아래의 3가지 조건을 제시했다.

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

 

무슨 말이냐하면,

1인 경우 그대로 0, 2인 경우 2/2 = 1과 2-1 = 1 두 가지가 존재한다.

다른 예로는 3이 1이 되려면, (3-1)/2 = 1과 3/3 = 1 두 가지가 존재한다.

 

X에 따른 최소 연산 수를 계산해보면, 아래와 같다.

1	2	3	4	5	6	7	8	9	10
0	1	1	2	3	2	3	3	2	3

 

 

점화식을 정리해보면,

dp[i] = dp[i/2] - 1

dp[i] = dp[i/3] - 1

dp[i] = dp[i-1] - 1

이므로 이 중에서 가장 작은 값을 골라하므로 min() 함수를 사용한다.

 

 

아래는 위의 원리를 사용한 C++ 코드이다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int n;
	cin >> n;
	
	vector<int> dp(n + 1, 0);


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

		if (i % 2 == 0) dp[i] = min(dp[i], dp[i / 2] + 1);
		if (i % 3 == 0) dp[i] = min(dp[i], dp[i / 3] + 1);
	}
	
	cout << dp[n];
}