[백준/BOJ] 1463 - 1로 만들기 (c++) (DP)

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

1463번: 1로 만들기

이번문제는 dp(다이나믹 프로그래밍)를 이용하여 푸는 문제이다.

 

예시들을 쭉 세워보면

 

n = 1은 0,

n = 2는 1,

n = 3은 1,

n = 4는 2,

n = 5는 3,

n = 6은 2

 

이다.

 

위의 예시들 중 n = 6을 보면

 

6은 3으로도 나누어 떨어지고, 2로도 나누어 떨어진다. 따라서 6을 3으로 나눈값, 2로 나눈값, 1을 뺸값을 다 비교해보아야한다.

 

즉 dp[6] = min(dp[6/3], dp[6/2], dp[6-1])이다.

 

이를 토대로 점화식을 세워보면

 

dp[i] = min(dp[i/3] (i%3이 0일때), dp[i/2] (i%2가 0일때), dp[i-1])이라고 할 수 있다.

 

---

#include <iostream>

using namespace std;

int n, mn, dp[1000006];

int main() {
	cin >> n;
	for (int i = 2; i <= n; i++) {
		int mn = 50;

		if (i % 3 == 0) mn = min(mn, dp[i / 3]);
		if (i % 2 == 0) mn = min(mn, dp[i / 2]);
		mn = min(mn, dp[i - 1]);

		dp[i] = mn + 1;
	}
	cout << dp[n];
}