[BOJ / C++] 1로 만들기 (BFS, 다이나믹 프로그래밍)

문제링크: https://www.acmicpc.net/problem/1463

 

> 방법 1: BFS 이용

1. 코드

#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;

    vector<int> dist(n+1, -1);
    queue<int> Q;

    dist[n] = 0;
    Q.push(n);
    
    while (dist[1] == -1) {
        int cur = Q.front(); Q.pop();
        
        if (cur % 3 == 0) {
            int nxt = cur / 3;
            if (dist[nxt] == -1) {
                dist[nxt] = dist[cur] + 1;
                Q.push(nxt);
            }
        }
        
        if (cur % 2 == 0) {
            int nxt = cur / 2;
            if (dist[nxt] == -1) {
                dist[nxt] = dist[cur] + 1;
                Q.push(nxt);
            }
        }
        
        int nxt = cur - 1;
        if (dist[nxt] == -1) {
            dist[nxt] = dist[cur] + 1;
            Q.push(nxt);
        }
    }

    cout << dist[1];
}

 

 

2. 분석

dist 배열을 -1로 잡고 각각 cur % 3 == 0, cur % 2 == 0, cur - 1 3가지 경우를 BFS로 돌린다.

 

3. 시간복잡도

dist 배열을 한번씩만 방문하므로 시간복잡도는 O(3n) = O(n)이고, n = 10^6 < 10^7이다. 또한 전부 계산하는 것이 아니라 dist[1] == -1일 때 멈추므로 실제 수행시간은 더 빠르다. 시간제한 0.15초내에 통과 가능하다.

 

 

 

> 방법 2: 다이나믹 프로그래밍 이용

1. 코드

#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;

    vector<int> dp(n+1, 0);
    dp[1] = 0;

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

 

 

2. 분석

1. 테이블 정의하기:

dp[i] = i 를 1로 만들기 위해 필요한 연산 사용횟수의 최솟값으로 테이블을 정의한다.

 

2. 점화식 찾기:

dp[k] = ?

3으로 나눠지면, 3으로 나누거나 (dp[k] = dp[k/3] + 1)

2로 나눠지면, 2로 나누거나 (dp[k] = dp[k/2] + 1)

1을 빼거나 (dp[k] = dp[k-1] + 1)

따라서 dp[k] = min(dp[k/3] + 1, dp[k/2] + 1, dp[k-1] + 1) 이 된다.

 

3. 초기값 정의하기: 

dp[1] = 0;

 

3. 시간복잡도

dp 배열을 한번 순회하므로 O(n)이고, 10^6 < 10^7이므로 시간제한 0.15초 내에 통과 가능하다.