[BOJ/C++] 1로 만들기(1463번)

1. 개요

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

1463번: 1로 만들기

1-1. 설명

 정수 X에 사용할 수 있는 연산은 다음과 같이 세가지이다.

 - X가 3으로 나누어 떨어지면, 3으로 나눔

 - X가 2로 나누어 떨어지면, 2로 나눔

 - 1을 뺌

정수 N이 주어졌을때, 위와 같은 연산 세 개를 적절히 사용해 1을 만드려고 한다. 연산을 사용하는 횟수의 최솟값을 출력한다. 

1-2. 제한 사항

 - 첫 줄에 1 이상 1,000,000 이하 정수 N이 주어짐

---

2. 구현

2-1. 풀이

다이나믹 프로그래밍의 Bottom-up인 반복문 방식으로 진행하였다. DP인건 인지했지만, 점화식을 구하는 것이 아직 어려워 다른 사람들의 풀이를 참고하여 풀었다. 조금 더 DP에 대해 연습해봐야겠다. 

2-2. 코드

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

int dp[1000000];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int num;
    cin >> num;

    dp[2] = 1, dp[3] = 1;

    for (int i = 4; i <= num; i++) {
        dp[i] = dp[i - 1] + 1; 
        if (i % 2 == 0) dp[i] = min(dp[i / 2] + 1, dp[i]);
        if (i % 3 == 0) dp[i] = min(dp[i / 3] + 1, dp[i]);
        // dp bottom-up
        // 1번 규칙 : dp[i] = dp[i/3] + 1 (3을 나눔)
        // 2번 규칙 : dp[i] = dp[i/2] + 1 (2를 나눔)
        // 3번 규칙 : dp[i] = dp[i-1] + 1 (1을 빼줌)
        // 위의 규칙 중 가장 작은 count 저장
        // 왜 (+ 1)? 이전 연산에서 현재 연산 횟수를 더해줘야 하므로
    }
    cout << dp[num];

    return 0;
}