[BOJ 1463] 1로 만들기 (2가지 풀이/DP/BFS) (C++)

www.acmicpc.net/problem/1463

1463번: 1로 만들기

1로 만들기 문제

구현 방법 (DP 풀이)

이 문제는 전형적인 DP(Dynamic Programming) 문제입니다.

 

DP문제를 해결하는 순서는 다음과 같습니다.

 

• 테이블 정의하기
• 점화식 찾기
• 초기값 정하기

이 문제에서 위 순서를 따라 답을 찾아보겠습니다.

---

• 테이블 정의하기

이 문제에서 테이블은 "D [i] = i를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값"이라고 정의할 수 있습니다.

테이블이란 이 문제에서 사용할 배열과 배열에 들어가는 각 값들의 의미입니다.

즉, 배열 d의 i번째에 들어가는 값은, i를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값입니다.

---

• 점화식 찾기

예를 들어 D [12]를 구하는 방법을 따라가며 점화식을 찾아보겠습니다.

 

12를 3으로 나누면    D[12] = D[4] + 1

12를 4로 나누면      D[12] = D[3] + 1

12에서 1을 빼면      D[12] = D[11] + 1

 

D [12]를 이뤄낼 수 있는 방법은 위처럼 3가지 방법이 있습니다. 이중 최솟값이 D[12]가 될 수 있습니다!

 

그럼 결국 D[12] = min(D[4] + 1, D[3] + 1, D[11] + 1)입니다

 

이를 점화식으로 표현하면 다음과 같습니다.

D[k] = min(D[k/3] + 1, D[k/3] + 1, D[k-1] + 1)

---

• 초기값 정의하기

이 문제는 1로 만드는 문제니 D[1] = 0으로 초기값을 설정해줘서 1에서 출발해 이 문제의 입력인 n까지 도달할 때까지 DP코드를 진해시켜 주시면 됩니다.

(1을 1로 만들려면 0번의 연산이 필요합니다!)

 

위 내용을 아래와 같이 소스코드로 구현했습니다.

 

소스코드 (DP 풀이)

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

int d[1000010];

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

    int n; cin >> n;

	//초기값 정의
    d[1] = 0;
	
    //1말고 2부터 n까지 for문 (점화식)
    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 풀이)

이 문제는 DP문제 지만, BFS로 풀 수 있습니다.

 

구현 방법은, d [1]부터 BFS를 해 나갑니다.

 

보통 BFS를 할 때 dx, dy배열을 사용해서 상하좌우를 확인하는 문제가 전형적인데, 이 문제는 1차원 배열을 사용하고, 상하좌우가 아닌 인덱스가 +1, x 2, x 3처럼 변합니다.

 

BFS를 뻗어 나가다가 n에 다다르는 순간 최소 경로 수를 출력해 주면 됩니다.

 

이 문제를 풀다가 막혔던 부분이 있습니다.

 

제가 생각했던 방법은, BFS를 해주면서, 방문 했었더라도, 이전에 방문해서 기록한 값보다 현재 방문해서 기록하는 값이 더 작으면 갱신해 주는 로직을 구현했습니다.

 

하지만 이는 BFS를 할때 큐에 반드시 거리순으로 저장되는 BFS의 성질을 제가 간과하고 있었습니다.

 

즉, 방문했었더라도, 이전에 방문해서 기록한 값보다 현재 방문해서 기록하는 값이 더 작을 경우의 수는 없습니다.

 

위 내용을 아래와 같이 구현했습니다.

 

소스 코드 (BFS 풀이)

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

int arr[1000005];
int dx[3] = {1,2,3};

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

    int n; cin >> n;
    arr[1] = 0;
    queue<int> Q;
    Q.push(1);
    while(!Q.empty()) {
        int cur = Q.front(); Q.pop();
        
        //종료 조건
        if(cur == n) {
            cout << arr[cur];
            return 0;
        }
        
        int nx;
        
        for(int dir=0;dir<3;dir++) {
        	
            //1칸 더하기
            if(dir == 0) {
                nx = cur + dx[0];
            }// x2 or x3
            else {
                nx = cur * dx[dir];
            }

            //범위 넘어가면 스킵
            if(nx > n) continue;
			
            //방문한적 없으면 연산횟수+1 저장
            if(arr[nx] == 0) {
                arr[nx] = arr[cur] + 1;
            }//방문한적 있으면 스킵
            else {
                continue;
            }

            Q.push(nx);
        }
    }
}