백준 14226 이모티콘

문제링크 : https://www.acmicpc.net/problem/14226

문제 접근

• BFS로 해서, 각 시간별 작업을 큐에 넣고 하면 되지 않을까
  • 큐 : 화면, 클립보드
  • 화면, 클립보드 중복 체크
    • 그래서 S개를 만드는데 시간 최소를 구하면 되지

시간복잡도 계산

• BFS 시간복잡도 O(V+E) : 4e6
• 노드 : 화면 * 클립보드 1e6
• 간선: 3개 * 노드
• O(V+E) : 4e6

인트 계산

• S는 1000개 이하, 시간도 그보다 이하
  

코드

#include <iostream>
#include <queue>
#include <map>
using namespace std;
 
// 스티커가 1000개 이상으로갔다가 떨어질 수도 있음
// 범위를 정하기가 애매해서 map으로 정의
map<pair<int, int>, bool> chk;
int main() {
    int S; cin >> S;
    queue<pair<int, int>> q;
    
    q.push(make_pair(1,0));
    chk[make_pair(1,0)] = 1;
    int t=0;
    while(!q.empty()) {
        int qsize =q.size();
        
        while(qsize--) {
            auto eq = q.front(); q.pop();
            int sc = eq.first;
            int cl = eq.second;
            if(sc == S) {
                cout << t << '\n';
                return 0;
            }
            
            // 클립보드에 복사
            if(chk[make_pair(sc,sc)] == 0) {
                q.push(make_pair(sc, sc));
                chk[make_pair(sc,sc)] = 1;
            }
            // 클립보드에서 붙여쓰기
            if(chk[make_pair(sc+cl,cl)] == 0) {
                q.push(make_pair(sc+cl, cl));
                chk[make_pair(sc+cl,cl)] = 1;
            }
            // 하나 제거
            if(sc>0) {
                if(chk[make_pair(sc-1,cl)] == 0) {
                    q.push(make_pair(sc-1, cl));
                    chk[make_pair(sc-1,cl)] = 1;
                }
                
            }
            
        }
        t++;
    }
    
    
    return 0;
}
 

문제유형

• 최소시간 구하는 BFS