[ 백준 ] 14226번 - 이모티콘 (C++)

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

14226번: 이모티콘

 

 

[ 문제풀이 ]

 

1. S를 입력받고, visited[ cur ][ copy ] 배열을 통해 현재 수와 클립보드에 저장된 수의 방문 여부를 체크합니다.

 

2. 다음의 세 경우를 queue에 넣어줍니다.

  - 복사 q.push({ cur, cur, cnt + 1 })

  - 붙여넣기 q.push({ cur + copy, copy, cnt + 1 })

  - 지우기 q.push({ cur - 1, copy, cnt + 1 })

 

3. S와 cur이 일치하면 cnt를 출력합니다.

 

[ 소스코드 ]

#include<iostream>
#include<queue>
 
using namespace std;
 
int S;
int visited[2001][2001];
 
struct node {
    int cur;
    int copy;
    int cnt;
};
 
int main()
{
    scanf("%d", &S);
 
    queue<node> q;
 
    q.push({ 1,0,0 });
 
    while (!q.empty()) {
        const int cur = q.front().cur;
        const int copy = q.front().copy;
        const int cnt = q.front().cnt;
        q.pop();
 
        if(cur > 2000) continue;
        if (visited[cur][copy] == 1) continue;
        visited[cur][copy] = 1;
 
        if (S == cur) {
            printf("%d", cnt);
            return 0;
        }
 
        q.push({ cur,cur,cnt + 1 });
        q.push({ cur + copy,copy,cnt + 1 });
        if (cur - 1 > 0) {
            q.push({ cur - 1,copy,cnt + 1 });
        }
    }
}