이모티콘 14226

문제

접근 방법

연산을 통해 특정 숫자를 만드는 문제는 BFS를 사용한다는 것을 본능적으로 알 수 있다.
클립보드의 존재로 인해 난감하겠지만 클립보드도 하나의 변수로 생각하면 쉽게 풀어낼 수 있다.
화면의 개수로만 방문 확인을 하면 같은 화면일지라도 클립보드의 개수가 달라 최소거리로 도달하는 것을 방해할 수 있다.
그렇기에 화면의 개수와 클립보드로 방문 확인을 하면 된다.

코드

#include <iostream>
#include <queue>
using namespace std;
bool visted[1001][1001];
struct node
{
    int screen, clip, time;
};
queue<node> q;
int S;
void push(node next)
{
    if (next.screen < 0 || next.screen > 1000 || visted[next.screen][next.clip])
        return;
    else if (next.screen == S)
    {
        cout << next.time;
        exit(0);
    }
    visted[next.screen][next.clip] = true;
    q.push(next);
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> S;
    if (S == 1)
    {
        cout << 0;
        return 0;
    }
    q.push({1, 0, 0});
    while (!q.empty())
    {
        node cur = q.front();
        q.pop();
        // 복사
        push({cur.screen, cur.screen, cur.time + 1});
        // 붙여넣기
        push({cur.screen + cur.clip, cur.clip, cur.time + 1});
        // 삭제
        push({cur.screen - 1, cur.clip, cur.time + 1});
    }
    return 0;
}

풀이

처음에는 방문 체크에만 집중해서 bool로 작성해뒀는데 int로 해두고 시간을 저장해도 좋을 것이다. 그렇게 하면 구조체가 아닌 pair로도 해결할 수 있다.

처음에는 방문 체크에 어떤 연산을 사용했는지도 넣었다. 하지만 생각해보면 빼 와서 사용하는 과정에서 3가지 연산을 모두 사용하기에 굳이 연산의 방문 체크를 할 필요가 없었다.

0 이하인 경우는 잊지 않고 예외 처리해줬는데 1000을 넘는 경우는 까먹고 못 해줘서 런타임 에러가 떴다.