백준, BOJ, 14226번, 이모티콘 C++ [CPP] ★★★

어렵지 않았다.

다만 어떻게 풀지? 가 관건이다.

 

 

 

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

 

---

 

문제 분석부터 해보자

 

 

최솟값을 가지는데 수행해야 하는 작업의 가중치가 같다?

BFS 가자

#include <bits/stdc++.h>

using namespace std;

//1개는 이미 입력
int S;

int visited[3000][3000];
int main(){
    cin >> S;
    //현재 상태, 클립보드에 저장된 개수
    
    queue<pair<int,int>> q;
    q.push({1,0});
    visited[1][0] = 1;
    
    while(!q.empty()){
        auto cur = q.front();
        q.pop();
        int now = cur.first;
        int clip = cur.second;
        
        
        //체크
        if(now == S){
            cout << visited[now][clip] - 1 << '\n';
            break;
        }
        
        
        //1.복사
        int nextClip = now;
        if(visited[now][nextClip] == 0){
            q.push({now, nextClip});
            visited[now][nextClip] = visited[now][clip]+1;
        }
        
        
        //2.붙여넣기
        if(now + clip <= S){
            if(visited[now+clip][clip] == 0){
                q.push({now+clip, clip});
                visited[now+clip][clip] = visited[now][clip]+1;
            }
        }
        
        //3.삭제
        if(now > 0){
            if(visited[now-1][clip] == 0){
                q.push({now-1, clip});
                visited[now-1][clip] = visited[now][clip]+1;
            }
        }
        
    }
    
    
    
    return 0;
    
}

 

어렵지 않지만 생각하기가 어렵고.. BFS에서 항상 주어지는 조건인 방문 가능 조건이 없어서 S를 이용해서 우리가 제거해주어야 한다.

즉, now - 1 이 0보다 작아지거나 now + clip이 S보다 커지는 것과 같은 일들을 없애주어야 한다.