Doby's Lab

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

PS/BOJ

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

도비(Doby) 2022. 10. 31. 23:03

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

 

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

7(A), 8(연산 1), 9(연산 1), 18(연산 2), 19(연산 1), 38(연산 2), 76(연산 2), 77(연산 1)이 최소 연산이므로 정답은 7이다.

www.acmicpc.net


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;
}

 

728x90

'PS > BOJ' 카테고리의 다른 글

백준 14430번: 자원 캐기 (C++)  (0) 2022.11.05
백준 1461번: 도서관 (C++)  (0) 2022.11.03
백준 1351번: 무한 수열 (C++)  (0) 2022.10.30
백준 14221번: 편의점 (C++)  (0) 2022.10.19
백준 12760번: 최후의 승자는 누구? (C++)  (0) 2022.09.17