<aside> 💡 1. 복사와 붙여넣기를 하나로 했을 때의 문제점 인식. → 복사 + 하나 빼기 + 붙여넣기가 안되기 때문에 오답이 나온다. 2. visited[s]로 했을 때의 문제점 인식. → 해당 visited[s]까지 bfs로 빨리 온다고 해서 그 경로가 무조건 최적이 아닐 수 있다.

</aside>

더 늦게 도착하지만 최적인 경로가 있을 수 있는데, (예를 들면 ssssss를 바로 복사해서 붙여넣는 것보다, 더 길게 만들어서 복사하고 붙여넣는게 빠를 수 있다) visited[s]를 통해서만 확인을 하면 이런 경우를 고려하지 못하기 때문에, visited[cur][clipboard]를 이용해서 현재위치와 그 위치에서의 복사된 항목까지도 고려해서 확인하는 것이 필요하다.

2차원 visited의 필요성을 인식하지 못해서 많이 헤맨 것 같다. 사실 지금도 음… 직관적으로 이해가 되지는 않는다. 2023년 5월 6일 오후 1:12 (GMT+9)

#include <bits/stdc++.h>
using namespace std;
#define fastio cin.tie(0)->sync_with_stdio(0)
#define endl '\\n';

using tp = tuple<int, int, int>;
using pp = pair<int, int>;
using ll = long long;

#define MAX 1001
int S, ans, visited[MAX][MAX];

void solve()
{
    memset(visited, -1, sizeof(visited));
    queue<pp> q;
    visited[1][0] = 0; // visited[cur][clipboard] = t
    q.push({1, 0});    // cur, clipboard

    while (!q.empty())
    {
        auto [cur, clipS] = q.front();
        int t = visited[cur][clipS];
        q.pop();

        // base case
        if (cur == S)
        {
            ans = t;
            return;
        }

        // 새로 복사하기
        if (visited[cur][cur] == -1)
        {
            visited[cur][cur] = t + 1;
            q.push({cur, cur});
        }

        // 붙여넣기
        const int pasteCur = cur + clipS;
        if (pasteCur < MAX && visited[pasteCur][clipS] == -1)
        {
            visited[pasteCur][clipS] = t + 1;
            q.push({pasteCur, clipS});
        }

        // 하나 삭제
        const int deleteCur = cur - 1;
        if (deleteCur > 0 && visited[deleteCur][clipS] == -1)
        {
            visited[deleteCur][clipS] = t + 1;
            q.push({deleteCur, clipS});
        }
    }
}

int main()
{
    fastio;
    cin >> S;

    solve();
    cout << ans << endl;

    return 0;
}