[백준] 1463 - 1로 만들기, C++

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

1463번: 1로 만들기

 본 문제는 DP 문제로 D[n] = min(D[n-1], D[n/3], D[n/2]) + 1 (n이 2 또는 3으로 나눌 수 있을 때의 점화식을 정의할 수 있다. DP문제는 중복되는 계산이 여러 번 등장하여야 하고, 큰 문제를 작은 문제에서 답을 구할 수 있어야 한다. 이때, 모든 반복되는 계산은 1번만 하도록 하여 계산 속도를 높인다.

1. n을 1로 뺀 경우의 수 계산하여 저장
2. n을 3으로 나눌 수 있을 때, n을 3으로 나눈 경우의 수와 1번을 비교하여 저장
3. n을 2로 나눌 수 있을 때, n을 2로 나눈 경우의 수와 2번을 비교하여 저장

Top-down

#include <cstdio>
 
using namespace std;
 
int d[1000001];
 
int cal (int n) {
    if (n == 1) return 0;
    if (d[n] > 0) return d[n];
    
    d[n] = cal(n-1) + 1;
    
    if (n % 3 == 0) {
        int tmp = cal(n/3) + 1;
        if (d[n] > tmp) d[n] = tmp;
    }
    
    if (n % 2 == 0) {
        int tmp = cal(n/2) + 1;
        if (d[n] > tmp) d[n] = tmp;
    }
    return d[n];
}
 
int main() {
    int n;
    scanf("%d", &n);
    
    int ans = cal(n);
    
    printf("%d", ans);
}
 

#include <cstdio>
 
using namespace std;
 
int main(){
    int d[1000001];
    int n;
    scanf("%d", &n);
    d[1] = 0;
    for (int i = 2; i <= n; i++) {
        d[i] = d[i-1] + 1;
        if (i%2 == 0 && d[i] > d[i/2]+1) d[i] = d[i/2]+1;
        if (i%3 == 0 && d[i] > d[i/3]+1) d[i] = d[i/3]+1;
    }
    printf("%d", d[n]);
}