#1463. 1로 만들기

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

1. 문제 이해

n을 입력 받았을때 나누기3, 나누기2, 빼기1 3가지 연산을 사용하여 1로 만들때, 최소 연산수를 구하는 문제 입니다.

2. 접근 방법

다이나믹 프로그램으로 문제 해결을 해보겠습니다. 

이 표현이 맞는지는 모르겠으나, 작은문제에서 큰문제를 해결해 나가는 bottom-up 방식으로 문제를 해결했습니다.

3. 문제 해결

for문으로 완전 탐색을 하되, 크게 3가지로 분류했습니다.

1. 3의 배수인가?                                => 3곱해서 올 수 있고, 1 더해서 올 수 있다.

2. 2의 배수인가?                                => 2곱해서 올 수 있고, 1 더해서 올 수 있다.

3. 3의배수, 2의배수 모두 아닐 경우        => 1더해서 밖에 올 수 없다.

이 루틴을 이용했습니다.

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