[BOJ 14266 // C++] 이모티콘

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 14266번 문제인 이모티콘이다.
문제는 아래 링크를 확인하자.

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

 

이모티콘이 $N$개 있는 상태에서 복사 연산을 한번 활용한 뒤 이후 새로 덮어쓰기 전까지의 붙여넣기 연산은 복사 직후에 몰아 하도록 소요 시간의 변화 없이 순서를 항상 조정할 수 있음을 관찰하자.

 

따라서 각 이모티콘의 상태에서 다음 상태로 가능한 상태들을 다음과 같이 좁혀 생각할 수 있다:

(1) 복사 후 연속하여 붙여넣기 연산만을 실행

(2) 이모티콘 하나를 삭제

 

위와 같은 간선의 개수는 생각보다 많지 않다. (조화급수를 생각해보자.) 따라서 이와 같은 그래프에서 dijkstra 알고리즘을 이용해 최소비용을 계산하는 것으로 문제를 충분히 빠르게 해결할 수 있다.

 

아래는 제출한 소스코드이다.

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

int dist[1001];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
void dijkstra() {
	memset(dist, 0x3f, sizeof(dist));
	pq.push(make_pair(0, 1));
	dist[1] = 0;
	while (!pq.empty()) {
		int cur = pq.top().second, d = pq.top().first; pq.pop();
		if (dist[cur] < d) continue;
		for (int k = 1; k < cur; k++) {
			int nxt = cur - k, dd = d + k;
			if (dd < dist[nxt]) dist[nxt] = dd, pq.push(make_pair(dd, nxt));
		}
		for (int nxt = cur, dd = d + 1; nxt < 1001; nxt += cur, dd++) {
			if (dd < dist[nxt]) dist[nxt] = dd, pq.push(make_pair(dd, nxt));
		}
	}
}

int N;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	dijkstra();

	cin >> N; cout << dist[N];
}