[BOJ] 1463번. 1로 만들기

사지방 시간이 없어서 급하게 올림.

문제 링크 : https://www.acmicpc.net/problem/1463

풀이:

숫자 10을 1로 만들 때, 10 9 3 1 이렇게 만들어진다.

D[i] : 숫자 i를 1로 만들 수 있는 최소 연산 횟수.

D[i] = MIN(D[i / 2], D[i / 3], D[i - 1]) + 1

단, D[i / 2], D[i / 3]은 i가 2로 나누어지거나, i가 3으로 나누어질 때만 참조 가능.

**** 주의. 나눌 수 있다고 해서 나눈 값으로 참조하면 최소값이 되지 않는다.

ex) 

  10 -> 9 -> 3 -> 1 과 10 -> 5 -> 4 -> 3 -> 1 중, 전자가 답이다.

#include <stdio.h>
#define MIN(x, y) x < y ? x : y
int D[1000001] = {0, 0, 1, 1};
 
int main() {
    int n = 0;
    
    scanf("%d", &n);
    
    for (int i = 4 ; i <= n ; i ++) {
        D[i] = 0x7fffffff;
 
        if (!(i % 3)) {
            D[i] = MIN(D[i / 3] + 1, D[i]);
        }
        if (!(i % 2)) {
            D[i] = MIN(D[i / 2] + 1, D[i]);
        }
        
        D[i] = MIN(D[i - 1] + 1, D[i]);
    }
    
    printf("%d", D[n]);    
    
    return 0;
}