BOJ-14226 이모티콘

필요한 지식

1. 힙

접근

한 상태에서 가능한 3가지 경우가 있다.

• 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
• 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
• 화면에 있는 모티콘 중 하나를 삭제한다.

한 상태에서 가능한 3가지 경우를 모두 봐주고 힙에 넣어준다.
힙에는 구조체 형태로

{시간,클립보드에 들어있는 길이, 화면에 표시된 길이} 이며, 최소 힙으로 구현한다.

체크 배열은 chk[클립보드에 들어있는 길이][화면에 표시된 길이] 로 중복 체크되는 경우를 해결했다.

코드(C++)

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
bool chk[2001][2001];
typedef struct Node {
	int time, clip, disply;
}node;
struct cmp {
	bool operator()(node t, node u) {
		return t.time > u.time;
	}
};
priority_queue<node, vector<node>, cmp> pq;
int go(int n) {
	while (!pq.empty()) {
		auto cur = pq.top();
		pq.pop();
		if (cur.disply >= 2001) continue;
		if (cur.disply == n) return cur.time;
		if (!chk[cur.disply][cur.disply]) {
			pq.push(node{ cur.time + 1,cur.disply,cur.disply });
			chk[cur.disply][cur.disply] = true;
		}
		if (cur.disply + cur.clip <= 2001 && !chk[cur.clip][cur.disply + cur.clip] && cur.clip) {
			pq.push(node{ cur.time + 1,cur.clip,cur.disply + cur.clip });
			chk[cur.clip][cur.disply + cur.clip] = true;
		}
		if (cur.disply > 1 && !chk[cur.clip][cur.disply - 1]) {
			pq.push(node{ cur.time + 1,cur.clip,cur.disply - 1 });
			chk[cur.clip][cur.disply - 1] = true;
		}
	}
	return 0;
}
int main() {
	int n; cin >> n;
	pq.push(node{ 0,0,1 });
	cout << go(n);
	return 0;
}