백준 25418번: 정수 a를 k로 만들기 (C++)

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

25418번: 정수 a를 k로 만들기

---

Solved By: DP

 

단순한 BFS로 구할 경우 중복된 값이 많이 들어가 시간 초과가 걸리게 됩니다. 그래서 중복체크를 하기 위해 Memoization 기법을 활용하여 BFS에 DP를 결합했습니다.

#include <iostream>
#include <queue>
#include <map>
#define pii pair<int, int>
using namespace std;

int n, k;
map<int, int> cache;

void bfs(){
    queue<int> q;
    q.push(n);
    cache[n] = 1;
    
    while(!q.empty()){
        int now = q.front();
        
        if(now == k){
            cout << cache[now] - 1;
            break;
        }
        
        q.pop();
        
        if(now > k) continue;
        
        if(!cache[now * 2]){
            cache[now * 2] = cache[now] + 1;
            q.push(now * 2);
        }
        if(!cache[now + 1]){
            cache[now + 1] = cache[now] + 1;
            q.push(now + 1);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> k;
    bfs();
    return 0;
}