알고리즘 :: 백준 :: DP :: 1463 :: 1로 만들기

문제링크

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
1) X가 3으로 나누어 떨어지면, 3으로 나눈다.
2) X가 2로 나누어 떨어지면, 2로 나눈다.
3) 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

문제 접근

1. 10은 `10->9->3->1'로 3번의 과정을 거치는 것이 가장 연산 횟수가 적다.
2. 임의의 숫자 n을 1로 만드는데 드는 가장 적은 연산 횟수를 기록해두면, 불필요한 연산 중복을 막을 수 있다는 점을 근거로 DP문제임을 알 수 있다.
3. 점화식 $D(N) = min(D(N-1),\ D(N/2),\ D(n/3))$
4. 구한 점화식을 그대로 코드로 옮긴다.

코드

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

static int n = 0;
static int cache[1000001];
// top-down 방식
int solve(int num) {
    if (num == 1) return 0;
    if (cache[num] > 0) return cache[num];

    cache[num] = solve(num - 1) + 1;  	// 1) n-1 먼저 구한다.
    if (num % 2 == 0) {             	// 2) 2로 나눠지는 경우
        int temp = solve(num / 2) + 1;
        if (cache[num] > temp) cache[num] = temp;
    }
    if (num % 3 == 0) {             	// 3) 3으로 나눠지는 경우
        int temp = solve(num / 3) + 1;
        if (cache[num] > temp) cache[num] = temp;
    }
    return cache[num];
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    memset(cache, 0, sizeof(cache));
    cout << solve(n) << '\n';
}

• 더 이상 분할할 수 없는 작은 문제 num = 1인 경우가 기저사례다.
• 이미 캐시에 저장되어 있는 값은 그대로 사용한다. 왜냐하면, 동일한 입력에 대해 동일한 답을 내는것이 DP의 전제이기 때문에 중복 연산할 필요가 없기 때문이다.
• n-1과 n/2 그리고 n/3의 비교는 어느것을 먼저하던지 상관없다.
• 본 코드의 방식은 top-down 방식이며 재귀를 사용하지 않는 bottom-up 방식은 다음과 같다.

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

static int n = 0;
static int cache[1000001];
// bottom-up 방식
int solve(int num) {
    cache[1] = 0;
    for (int i = 2; i <= num; ++i) {
        cache[i] = cache[i - 1] + 1;
        if (i % 2 == 0 && cache[i] > cache[i / 2] + 1) cache[i] = cache[i / 2] + 1;
        if (i % 3 == 0 && cache[i] > cache[i / 3] + 1) cache[i] = cache[i / 3] + 1;
    }
    return cache[num];
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    memset(cache, 0, sizeof(cache));
    cout << solve(n) << '\n';
}

결과