백준 1463번: 1로 만들기 (C++) - BFS / DP

문제

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

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

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

• 입력
  • 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
• 출력
  • 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

코드

1. BFS

#include <iostream>
#include <queue>
#include <utility>
using namespace std;

int arr[1000002];

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    queue<int> q;

    arr[1] = 0;
    q.push(1);

    while(!q.empty()){
        int cur = q.front();
        q.pop();

        if(cur == n){
            cout << arr[cur];
            return 0;
        }

        for(int i = 0; i < 3; i++){
            int next;
            if (i == 0) next = cur + 1;
            else next = cur * (i + 1);

            if(next > n) continue;
            if(arr[next] == 0) arr[next] = arr[cur] + 1;
            else continue;

            q.push(next);
        }
    }
}

2. DP

#include <iostream>
using namespace std;

int d[1000002];

int main(void){
    int n;
    cin >> n;

    d[1] = 0;

    for(int i = 2; i <= n; i++){
        d[i] = d[i - 1] + 1;
        if(i % 2 == 0) d[i] = min(d[i], d[i/2] + 1);
        if(i % 3 == 0) d[i] = min(d[i], d[i/3] + 1);
    }

    cout << d[n];
    
}

접근 및 풀이

요즘은 다이나믹 프로그래밍을 공부하는 중이라 다이나믹 프로그래밍 관련 문제를 푸는데 이 문제는 BFS로도 풀 수 있을 것 같아서 두 가지 풀이로 풀어봤다. 전에 백준에서 비슷한 문제를 푼 적 있어서 BFS 풀이법부터 생각난 것 같다. 참고로 비슷한 문제는 백준 1697: 숨바꼭질 (링크) 이다. 이전에 BFS 문제 분석할 때 풀이법에 대해서도 간단히 다룬 적이 있으니 궁금한 사람들은 참고해 보면 좋을 것 같다.

먼저 BFS로 풀 때는 1에서부터 시작해서 1을 더하거나 / 3을 곱하거나 / 2를 곱하는 방법으로 배열에 \(10^6\)까지의 연산 횟수를 모두 기록한다. 그럼 N이 무엇이든지 배열의 값만 뽑아내면 된다.

DP로 풀 때는 점화식을 만든 다음 초기값부터 정의해야 한다. 3으로 나누어지면 3으로 나누거나 / 2로 나누어지면 2로 나누거나 / 1을 뺀 방법 중 최솟값을 선택하면 되는데, 여기에서는 d[i - 1]을 점화식에서 사용해야 하니 d[0]과 d[1]이 필요하지만 d 배열이 모두 0으로 초기화 되어 있으니 d[0]을 0으로 따로 정의해야 할 필요는 없다. 물론 d[0]이 0이 아닌 경우에는 새로 정의해야 한다.

확실히 DP로 푸는 방법이 더 짧고 간단하지만 조건이 많고 까다로운 문제에서는 점화식을 만들기가 어려울 것 같다. 대부분의 문제들이 다른 풀이법이 있지만 DP로도 풀 수 있는 문제들이 많다고 한다. 아직은 DP 문제를 많이 접해보지 않아서 점화식 만들기가 좀 힘든 것 같다. 굵은 뼈대는 잡을 수 있지만 잔조건들이 많으면 그것까지 생각하기 힘든… 그래도 숙달되면 금방 할 것 같긴 하다.