Baekjoon 14226번 이모티콘

문제

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

걸린 시간

01 : 28 : 11

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int s;
queue<pair<int, int>> q; // count, clipboard
map<pair<int, int>, int> cache;

int bfs(){
    q.push(make_pair(1, 0));
    cache[make_pair(1, 0)] = 1;
    int depth = -1;
    while(!q.empty()){
        depth++;
        int size = q.size();
        for(int i = 0; i < size; i++){
            int count = q.front().first;
            int clip = q.front().second;
            q.pop();
            if(count == s) return depth;
            if(!cache[make_pair(count, count)]){
                q.push(make_pair(count, count)); // 1
                cache[make_pair(count, count)] = 1;
            }
            if(clip != 0){
                if(!cache[make_pair(count+clip, clip)]){
                    q.push(make_pair(count+clip, clip)); // 2
                    cache[make_pair(count+clip, clip)] = 1;
                }
            }
            if(count > 0){
                if(!cache[make_pair(count-1, clip)]){
                    q.push(make_pair(count-1, clip)); // 3
                    cache[make_pair(count-1, clip)] = 1;
                }
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> s;
    cout << bfs();
    return 0;
}

현재 이모티콘의 개수와 클립보드에 저장된 이모티콘의 개수를 쌍으로 메모이제이션하며 bfs 탐색을 진행하면 된다.

예제를 손으로 풀어볼 때 빠르게 직관을 얻으려면 각 단계마다 사용되는 값들을 전부 표현하는 것이 좋을 것 같다.