1463번 1로 만들기 - DP

#include <stdio.h>

int memo[1000001] = {9999999, };  //메모리제이션

int min(int a, int b, int c)
{
    if(a<b)
        if(a<c)  //a<b,c
            return a;
        else  //c<a<b
            return c;
    else if(b>c)  //a>b>c
        return c;
    else  //b<a,c
        return b;
}

int f(int N, int cnt)
{
    int a=0, b=0, c=N-1;
    
    if(N==1)
        return cnt;
    if(memo[N]) //기록되어있으면 쓰기
        return memo[N]+cnt;
    
    if(N%3 == 0)
        a=N/3;
    if(N%2 == 0)
        b=N/2;  
    
    memo[N] = min(f(a, cnt+1), f(b, cnt+1), f(c, cnt+1)) - cnt;
    return memo[N] + cnt;
    
}

int main()
{
    int N; memo[1]=1;
    
    scanf("%d", &N);
    
    printf("%d", f(N, 0));
    
    return 0;
}

 

메모리제이션을 써서 /3, /2, -1로 3가지로 나눠서 풀면 될 거라고 생각했는데 다른 사람들의 풀이를 보면

-1을 하는 이유는 /3, /2를 맞춰주기 위한 거라서 그냥 /3, /2로 두 가지로만 케이스를 나누면 됬었고, /2, /3하는 과정에서 겹치지도 않아서 메모리제이션을 할 필요도 없었다. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ;;