[백준] 1로 만들기 C++ 두가지 풀이 BFS, DP

문제

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

이전 포스트인 동전1,2를 풀며 비슷했던? 문제를 가져왔다.

이것도 특정 값이 되는 최소의 경로를 찾는 문제이다.

동전과 다른점은 배수가 된다는 점? 이다.

 

 

---

풀이1 DP

이전 포스트 였던 동전2에서는 DP배열에 동전을 하나 하나 해봤다.

그이유는 어떤 경로이든 상관없기때문, 하지만 이번엔 배수와 덧셈으로 전진하므로 그렇겐안된다.

예를들어

1 에서 (+1) (*2)

1 에서 (*2) (+1) 은 그 결과값이 다르기때문이다. 경로가 달라지면 값도 바뀐다.

따라서 한번의 값마다 3가지 방법을 통해 최단 경로를 갱신해준다.

for(int i = 2 ; i <= n ; 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);
    }

 

 

---

소스코드1 DP

#include <iostream>

int n;
int dp[1000005];
using namespace std;
int cnt = 0;

int main(){
    int n;
    cin >> n;
    dp[1] = 0;
    for(int i = 2 ; i <= n ; 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 BFS

BFS는 가중치가 없는 간선이면 이전 지점 + 1을 하는 방법을 통해 최단 거리를 구하는게 보장된다.

따라서 3개의 이동 조건만 만들어주면, 목적지에 닿는 최단 거리를 구할 수 있게된다.

 

 

 

 

 

---

소스코드2  BFS

#include <bits/stdc++.h>

using namespace std;

const int INF = 1000001;
int dis[1000001];
int N;

void BFS(int cur){
    dis[cur] = 0;
    queue <int> q;
    q.push(cur);
    while(!q.empty()){
        cur = q.front();
        q.pop();
        int dx[3] = {cur+1, cur*2, cur*3};
        for (int i = 0; i < 3; ++i) {
            int nx = dx[i];
            if(nx > N) continue;
            if(dis[nx]!=0) continue;

            q.push(nx);
            dis[nx] = dis[cur] + 1;
        }

    }
}

int main(){
    cin >> N;
    BFS(1);
    cout << dis[N];
}