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

문제 링크

1463번: 1로 만들기

 

풀이 ) DP

  1은 연산할 필요가 없으므로 0이고, 2와 3은 각각 2번 1번 연산을 통해서 1이 될 수 있다.

  그 이후인 memo[n]에 대해서는 처음에 memo[n-1] + 1의 값을 저장한 후

  3으로 나누어 떨어진다면 현재 저장된 값과 memo[n/3] + 1의 값을 비교하여 더 적은 값을 memo[n]에 저장한다.

  마찬가지로 2로 나누어 떨어진다면 현재 저장된 값과 memo[n/2] + 1의 값을 비교하여 더 적은 값을 memo[n]에 저장한다.

 

#include <cstdio>
#include <algorithm>
using namespace std;

int memo[1000002] = {0, 0, 1, 1};

int main(void)
{
    int n;
    scanf("%d", &n);

    for(int i = 4; i <= n; i++){
        memo[i] = memo[i-1]+1;
        if(i%3==0) memo[i] = min(memo[i], memo[i/3]+1);
        if(i%2==0) memo[i] = min(memo[i], memo[i/2]+1);
    }
    printf("%d\n", memo[n]);
    return 0;
}