[C++] 백준 1463번:1로 만들기(DP)

문제링크

1463번: 1로 만들기

문제

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

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

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

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

풀이

다이나믹 프로그래밍 방식(DP)을 이용하여 풀이해야 한다.

미리 만들어둔 배열의 index는 실제 해당 값을 의미한다.

각각의 수(index)에 대해 1,2,3번의 연산을 진행했을 때 최소로 진행하여 1을 만들 수 있는 횟수를 배열에 저장해준다. 그러면 그보다 큰 수를 1로 만들 때 최소로 진행하는 횟수를 더 쉽게 구할 수 있게 된다.

9와 10에 대해 예를 들어 설명해보겠다.

9는 9 → 3 → 1 을 통해 1을 만들 수 있기 때문에 총 2번의 연산이 필요하다.

10을 1로 만들 수 있는 경우의 수는 다양하지만 최소 연산의 횟수를 찾아야 한다.

1. 3번 연산을 진행했을 때
   • - 3번 연산을 진행하면 10 → 9가 되고 9가 1이 되기 위해서는 앞에서 미리 2번의 연산이 필요하다는 것을 알고 있다. 따라서 3번 연산을 한번 진행했기 때문에 9를 1로 만드는 연산의 횟수에 1을 더해주면 된다.
2. 2번 연산을 진행했을 때
   • 2번 연산을 진행하면 10은 5가 된다. 5를 1로 만들기 위해서는 총 3번의 연산이 필요하고 이는 앞에서 미리 구해서 배열에 저장했다.
3. 1번 연산을 진행했을 때
   • 10은 3으로 나누어지지 않기 때문에 1번 연산을 진행할 수 없다.

따라서 최소 연산의 횟수는 3이고 10은 10 → 9 → 3 → 1 을 통해 1을 만들 수 있기 때문에 총 3번의 연산이 필요하다는 것도 증명이 된다.

코드

#include <iostream>
using namespace std;
 
int n;
int arr[1000001];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    arr[0] = 0;    // 0을 1로 만드는 연산의 횟수는 0
    arr[1] = 0;    // 1을 1로 만드는 연산의 횟수는 0
    cin >> n;
    
    for (int i = 2; i <= n; i++) {
        // 3번연산
        arr[i] = arr[i - 1] + 1;
        // 2번 연산
        if (i % 2 == 0) {
            arr[i] = min(arr[i], arr[i / 2] + 1);
        }
        // 1번 연산
        if (i % 3 == 0) {
            arr[i] = min(arr[i], arr[i / 3] + 1);
        }
    }
 
    cout << arr[n];
 }

 

메모

다이나믹 프로그래밍(DP) 방식의 풀이는 경험이 많지 않아서 이번 문제를 푸는데 한 시간 정도 고민하고 힌트를 찾아가며 풀어보았다.

다이나믹 프로그래밍에 관해 더 알고 싶으시다면 다음 게시물로 가셔서 보시는 것을 추천 드립니다.

다이나믹 프로그래밍(DP)