문제 링크

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

해결 팁

1. 클립보드 복사를 했는지 안했는지 알 수 없기 때문에 clip 변수를 struct에 선언한다.
2. visited 를 2차원으로 선언하여 [다음화면][클립보드] 에 따라 확인한다.
3. 가장 빠른 방법을 찾아야 하므로 BFS를 사용하며 가지치기를 하며 진행한다.

코드

#include <iostream>
#include <queue>

#define endl "\n"

using namespace std;

int s;
int visited[1001][1001] = { 0, };

struct node
{
	int cur;
	int cnt;
	int clip;
};

queue<node> q;


void bfs()
{
	q.push({ 1,0,0 });
	visited[1][0] = 1;

	while (!q.empty())
	{
		int cur = q.front().cur;
		int cnt = q.front().cnt;
		int clp = q.front().clip;

		q.pop();

		if (cur == s)
		{
			cout << cnt;
			return;
		}
		// 복사하기 : 현재 화면을 복사하려는데 복사한걸 또 복사하면 안되고, 복사 한 후 상태가 visited 0 이면
		if (!visited[cur][cur])
		{
			visited[cur][cur] = 1;
			q.push({ cur, cnt + 1 , cur });
		}

		// 붙여넣기 : 현재 화면 + clip 보드 에 저장된 값을 더하는것
		if (cur + clp <= s && !visited[cur + clp][clp])
		{
			visited[cur + clp][clp] = 1;
			q.push({ cur + clp, cnt + 1, clp });
		}

		// 화면에서 1빼기 : 현재 화면 - 1 해주는것.
		if (cur - 1 >= 0 && !visited[cur - 1][clp])
		{
			visited[cur - 1][clp] = 1;
			q.push({ cur - 1, cnt + 1, clp });
		}
	}
}

int main()
{
	cin >> s;

	bfs();

	return 0;
}

후기

처음에는 next 함수를 만들어서 인덱스에 따라 다음 화면의값을 받아 진행했는데 여기서 vistied의 조건때문에 2시간 정도 해메다가 if 문으로 나누어 작성.