[BOJ/백준][Gold5] 14226 : 이모티콘 (C++)

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

14226번: 이모티콘

 

 

[난이도] Gold5
[유형] BFS

[풀이]
visit[a][b] 배열을 이용해 BFS를 진행한다. a:현재 이모티콘의 수, b:클립보드에 복사되어 있는 이모티콘의 수
S의 최댓값이 1000이므로 배열의 크기는 1500으로 여유롭게 잡는다. 클립보드에 있는 이모티콘을 복사하면 1000을 넘을 수 있지만 2000을 넘기는 것은 의미가 없으므로 1500으로 잡았더니 AC를 받았다.

 

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
int S,visit[1500][1500];
int main(){
    scanf("%d",&S);

    queue<pair<int,int>> q;
    visit[1][0]=1;
    q.push({1,0});
    int ans =0;
    while(!q.empty()){
        int sz=q.size();
        while(sz--){
            int a = q.front().first;
            int b = q.front().second; q.pop();
            if(a==S) {
                printf("%d",ans);
                return 0;
            }
            if(a-1>=0 && !visit[a-1][b]){
                visit[a-1][b]=1;
                q.push({a-1,b});
            }
            if(b>0 && a+b < 1500 && !visit[a+b][b]){
                visit[a+b][b]=1;
                q.push({a+b,b});
            }
            if(!visit[a][a]){
                visit[a][a]=1;
                q.push({a,a});
            }
        }
        ans++;
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/14226.cpp