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

#include <iostream>

int main(int argc, char **argv){
    int dp[1000001] = {0}; //dp -> 반대로 생각해서 채우기
    int x;
    scanf("%d",&x);

    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 1;

    for(int i = 4; i <= x; i++){ // 전부 다 구할 필요 없다.
        // 제일 적은 연산 + 1 = 제일 작은 연산값
        dp[i] = dp[i-1] + 1;
        if((i % 3) == 0){ // 배수인 것 구해야
            if((dp[i/3] + 1) < dp[i]){
                dp[i] = dp[i/3] + 1;
            }
        }
        if((i % 2) == 0){ //else if 대신
            if((dp[i/2] + 1) < dp[i]){
                dp[i] = dp[i/2] + 1;
            }
        }
        // 그냥 dp[i/3] < dp[i/2] && dp[i/3] < dp[i-1] 나누기 하면 안되는 이유 4/3 = 1 (정수화 된다)
    }

    printf("%d",dp[x]);

    return 0;
}

오늘의 키포인트

• 최소를 구할때는 거꾸로 생각하자. 최소 + 최소 = 최소 (다이나믹 프로그래밍)

• for문을 모든 범위 다 돌릴 필요 없다. 특히나 값 하나만 구하면 되는 경우에는

• 그냥 dp[i/3] < dp[i/2] && dp[i/3] < dp[i-1]로 구하면 안되는 이유는 4/3 = 1이 되기 때문이다.

• if문과 else if문은 다르다. i가 2로 나누어 떨어질 때와 3으로 나누어 떨어질 때, 두 가지의 경우 사이에서 더 작은 값을 찾아야하기에 if문을 두 번 사용해야한다. else if문 사용시, 6의 배수로 나누어 떨어지는 경우에는 3으로 나누어 떨어질 때의 최소값만 구하고 끝이 난다.