백준1463번: 1로 만들기

초기 접근 방법

일단 나는 처음에 최소 횟수를 구하는 문제이기 때문에 단순하게 재귀를 사용해 DFS+백트래킹 문제처럼 접근했다. 하지만, 이렇게 하면 최소값 비교가 안될 뿐더러 먼저 도착한 경로가 최소라고 보장 못하는 문제가 생간다.

즉, 이 문제는 DP(Dynamic Programming, 동적 계획법)을 사용하여 풀어야 한다. 동적 계획법이란 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하고, 다시 큰 문제를 풀 때 해결하는 알고리즘이다. 이걸 이 문제에 적용하면, 현재 값의 최소 횟수는 이전 최소값들로부터 온다라는 개념을 이용해 풀어야 한다.

---

점화식 구하기

(1) DP를 표로 떠올리기

n     dp[n]
------------
1      0
2      1   (2 → 1)
3      1   (3 → 1)
4      2   (4 → 2 → 1)
5      3   (5 → 4 → 2 → 1)
6      2   (6 → 3 → 1)
7      3   (7 → 6 → 3 → 1)
8      3   (8 → 4 → 2 → 1) 
9      2   (9 → 3 → 1)
10     3   (10 → 9 → 3 → 1)

n의 답은 더 작은 값들의 답을 기반으로 결정된다!

즉, dp[n]을 정수 n을 1로 만드는 최소 연산 횟수라고 정의하고 문제를 풀어보자.

(2) 점화식

dp[n] = dp[n-1] + 1
if (n % 2 == 0) dp[n] = min(dp[n], dp[n/2] + 1)
if (n % 3 == 0) dp[n] = min(dp[n], dp[n/3] + 1)

---

정답 코드

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

int dp[1000001];

int main() {
    int n;
    cin >> n;

    dp[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] << endl;
    return 0;
}