BOJ 1463 · 1로 만들기

알고리즘 분류 : 다이나믹 프로그래밍  

기초적인 DP문제이다. 3가지 조건을 따져서 점화식을 만들고, 이를 구현하면 된다.

• D[N] : N을 1로 만드는 최소 연산 횟수
• D[1] = 0
• D[N-1] + 1 : N에서 1을 뺀 경우
• D[N/3] + 1 : N을 3으로 나눈 경우
• D[N/2] + 1 : N을 2로 나눈 경우

---

C++ 소스코드

#include <cstdio>

int d[1000001];

int solve(int n) {
    d[1] = 0;
    for (int i=2; i<=n; i++) {
        d[i] = d[i-1]+1;
        if (i%3 == 0) {
            int temp = d[i/3]+1;
            if (d[i] > temp) d[i] = temp;
        }
        if (i%2 ==0) {
            int temp = d[i/2]+1;
            if (d[i] > temp) d[i] = temp;
        }
    }
    return d[n];
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", solve(n));
    return 0;
}

---

Python 3 소스코드

def solve(n):
    d = [0]*(n+1)
    for i in range(2, n+1):
        d[i] = d[i-1]+1
        if i%3 == 0:
            temp = d[i//3]+1
            d[i] = min(d[i], temp)
        if i%2 == 0:
            temp = d[i//2]+1
            d[i] = min(d[i], temp)
    print(d[n])

solve(int(input()))

---

참고

• 백준 온라인 저지 : BOJ 1463