백준 1463번 : 1로 만들기

링크 : https://www.acmicpc.net/problem/1463

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

int dp[1000000];

int main() {
	int  num;
	
	cin >> num;
	for (int i = 2; i <= num; ++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[num] << endl;
	return 0;
}

int dp[1000000]; 이걸 int main() 밖으로 빼야 한다. 경고가 뜨는데 이유는 모르겠다.

dp 배열을 생성하여 인덱스의 숫자가 어떻게 구해졌는지 계산하고 최솟값을 저장해놓는 것이다.
0과 1은 2, 3의 계산으로 나올 수 없으므로 dp[0] = dp[1] = 0; 으로 설정해준다. 그 이후의 계산을 들여다보자.

2의 경우 (1*2 = 2), (1+1 = 2)의 연산이 가능하고 최소 연산은 1번이다. 이렇게 진행되다가 6의 경우, (5까지의 연산)+1 이 되거나 (2까지의 연산)+1(3 곱하기), (3까지의 연산)+1(2 곱하기)가 가능해진다.

즉 점화식을 세우는 것이 중요해진다.

• n = (n-1)+1 -> dp[i] = dp[i-1]+1 : 임의의 dp[i] 설정. 기본적으로 모든 연산은 전 단계의 연산에 1을 더한 것과 같다. 아래의 dp[i]에는 기본적으로 이 값이 들어간다. 아래의 연산들은 이렇게 계산된 값에 비해 *2 또는 *3 으로 되었을 때 더 작은 수가 들어갈 수 있을 것인가에 대한 탐구 계산이다.
• n = (n/2)*2 -> dp[i] = min(dp[i], dp[i/2]+1) : +1은 *2의 연산 횟수가 더해진 것)
• n = (n/3)*3 -> dp[i] = min(dp[i], dp[i/3]+1) : +1은 *2의 연산 횟수가 더해진 것)

이러한 연산은 찾고자 하는 num까지 진행하면 되는 것이다.