[백준 / BOJ / SILVER 3] 1463 번 : 1로 만들기

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

1463번: 1로 만들기

문제 접근법

• 제일 작은 수 부터 X까지 갈때의 경우의 수를 구한다.
• 해당하는 배열에 가장 작은 경우의 수를 넣는다.

아래는 코드입니다.

#include <cstdio>
#include <algorithm>
 
using namespace std;
 
int check[1000001];
 
int main()
{
    check[1] = 0;
 
    int n;
    scanf("%d", &n);
 
    for (int i = 2; i <= n; i++)
    {
        check[i] = check[i - 1] + 1;
 
        if (i % 2 == 0)
        {
            check[i] = min(check[i], check[i / 2] + 1);
        }
        if (i % 3 == 0)
        {
            check[i] = min(check[i], check[i / 3] + 1);
        }
    }
 
    printf("%d", check[n]);
 
    return 0;
}