백준 14226번: 이모티콘

[문제 링크]

14226번: 이모티콘

---

간단한 bfs 문제였다.

문제에 주어진 3가지 방법을 각각 구현하여 이를 수행한 3가지 결과를 큐에 담아주도록 구현하였다.

방문 체크는 이모티콘의 개수 뿐만이 아니라 클립보드에 저장된 이모티콘의 개수에 따라서도 결과가 바뀔 수 있기 때문에 2차원 visited 배열을 선언하였다.

 

visited 배열 대신 memo 배열을 통해 메모이제이션 기법을 활용하여 풀이한 코드도 추가하였다.

---

// bfs

#include <iostream>
#include <queue>
using namespace std;

bool visited[2001][2001];

struct info {
	int cnt;
	int clipBoard;
	int time;
};

int bfs(int S) {
	int start = 1;
	queue<info> q;
	q.push({ start, 0, 0 });
	visited[start][0] = true;

	while (!q.empty()) {
		int cnt = q.front().cnt;
		int clipBoard = q.front().clipBoard;
		int time = q.front().time;
		q.pop();

		if (cnt == S)
			return time;

		// case 1
		if (!visited[cnt][cnt]) {
			q.push({ cnt, cnt, time + 1 });
			visited[cnt][cnt] = true;
		}

		// case 2
		if (cnt+clipBoard < 2000 && !visited[cnt + clipBoard][clipBoard]) {
			q.push({ cnt + clipBoard, clipBoard, time + 1 });
			visited[cnt + clipBoard][clipBoard] = true;
		}

		// case 3
		if (cnt - 1 > 0 && !visited[cnt - 1][clipBoard]) {
			q.push({ cnt - 1, clipBoard, time + 1 });
			visited[cnt - 1][clipBoard] = true;
		}
	}

	return -1;
}
int main(void) {
	int S;
	cin >> S;

	cout << bfs(S) << endl;

	return 0;
}

// dp

#include <iostream>
#include <algorithm>
using namespace std;

int memo[2001][2001];
const int INF = 987654321;

int dp(int here, int clipBoard, int S) {
	if (here < 0 || here > S*2 || clipBoard > S*2) return INF;
	if (here == S) return 0;

	int& ret = memo[here][clipBoard];
	if (ret != 0) return ret;
	ret = INF;

	int case1 = dp(here, here, S) + 1;
	int case2 = dp(here - 1, clipBoard, S) + 1;
	int case3 = dp(here + clipBoard, clipBoard, S) + 1;

	ret = min(ret, min(case1, min(case2, case3)));
	return ret;
}

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

	cout << dp(1, 0, S) << endl;

	return 0;
}