1463번: 1로 만들기(10분)

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

구현 아이디어 5분 구현 5분

풀이

예)
6의 경우에는 5로 가서(Dp[5]) 3번 수행하는 방법,
6은 3으로 나눠지니까 2로 가서 1번 수행하는 방법,
6은 2로 나눠지니까 3으로 가서 1번 수행하는 방법 중 최소를 찾아 Dp 배열에 넣어준다.

7의 경우에는 6으로 가서 2번 수행하는 방법,
7은 2 혹은 3으로 나눠지지 않기 때문에 비교할 최솟값이 없다.

8의 경우 7로 가서 3번 수행하는 방법,
3으로는 나눠지지 않기 때문에 넘어가고,
2로 나눠지기 때문에 4로 가서 2번 수행하는 방법 중 최소를 찾아 Dp 배열에 넣어준다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int Dp[1000001];
int N{};

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

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

    for (int i = 4; i <= N; ++i)
    {
        int Case1 = 2147000000, Case2 = 2147000000, Case3 = 2147000000;
        
        Case1 = Dp[i - 1] + 1;
        if (i % 2 == 0)
        {
            Case2 = Dp[i / 2] + 1;
        }
        if (i % 3 == 0)
        {
            Case3 = Dp[i / 3] + 1;
        }

        Dp[i] = min(Case1, Case2);
        Dp[i] = min(Dp[i], Case3);
    }

    printf("%d", Dp[N]);

    return 0;
}