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

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

14226번: 이모티콘

 

문제조건

- 이모티콘의 개수를 늘리는 방법은 오직 붙여넣기 뿐이다. 화면의 이모티콘은 임의로 늘릴 수 없으나 삭제는 가능하다. 그리고 각 행동은 1초의 작업시간을 가진다. 

 

내 접근

- 당연히 BFS 문제라고 생각했다. 최소,최단거리 문제이고 할 수 있는 행동이 3가지이다. 그러므로 BFS문제라 생각하는 것이 타당하다. 그러나 문제는 방문처리이다. 한 번 갔던 이모티콘 개수라 해도 담고있는 클립보드의 수도 고려해야한다. 그래서 visited 를 2차원으로 구성하고 visited[이모티콘개수][클립보드의이모티콘개수] 이것으로 방문체크를 해야한다. 이것까지만 고려하면 그리 어려울 것 없는 문제이다.

 

올바른 접근법

- 내 풀이가 정해가 맞지만 DP로도 구할 수 있는 듯하다. 

 

#include <iostream>
#include <queue>

using namespace std;

queue<pair<pair<int, int>, int>> q;

bool visited[1001][1001] = {false,};
int main() {
	int d;
	cin >> d;

	q.push({ {1,0},0 });
	visited[1][0] = true;
	int answer = 4554657865;
	while (!q.empty()) {
		int N = q.front().first.first;
		int ClipValue = q.front().first.second;
		int cnt = q.front().second;
		q.pop();

		if (cnt > answer)
			continue;

		if (N == d) {
			answer = min(answer, cnt);
			continue;
		}

		if (N - 1 > 0 && visited[N - 1][ClipValue] == false) {
			visited[N - 1][ClipValue] = true;
			q.push({ { N - 1, ClipValue }, cnt + 1 });
		}
		if (ClipValue != 0 && N + ClipValue < 1001) {
			if (visited[N + ClipValue][ClipValue] == false) {
				visited[N + ClipValue][ClipValue] = true;
				q.push({ { N + ClipValue, ClipValue }, cnt + 1 }); // 붙여넣기
			}
		}
		if (visited[N][N] == false && N < 1001) {
			visited[N][N] = true;
			q.push({ {N, N,}, cnt + 1 }); // 복사하기
		}
	}

	cout << answer << '\n';
}