[백준] 1463번 1로 만들기

문제

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

풀이과정

기본적인 DP 문제 중 하나이다. D[i] = i를 1로 만드는 데 필요한 최소 연산 횟수라고 놓고 경우의 수를 생각해보니 아래와 같았다.

1. i가 3으로 나누어 떨어질 경우

   D[i/3] + 1

2. i가 2로 나누어 떨어질 경우

   D[i/2] + 1

3. i에서 1을 빼는 경우

   D[i-1] + 1

이렇게 총 세 가지이며 세 가지의 경우 중 최소값을 찾으면 된다.

소스코드

#include <iostream>

using namespace std;

#define MAX 1000001

int D[MAX];

int solution(int N)
{
    if (N==1) return 0;
    if (D[N] > 0) return D[N];

    D[N] = solution(N - 1) + 1;

    if (N % 2 == 0)
    {
        int tmp = solution(N / 2) + 1;
        if (D[N] > tmp) D[N] = tmp;
    }

    if (N % 3 == 0)
    {
        int tmp = solution(N / 3) + 1;
        if (D[N] > tmp) D[N] = tmp;
    }

    return D[N];
}
int main()
{
    int N;

    cin >> N;

    cout << solution(N);

    return 0;
}