JUST WRITE IT. HomeArchivesTagsCategories
백준 14226번 이모티콘
|AlgorithmBOJ|

#14226. 이모티콘

Problem

Solution

  1. 화면에 있는 이모티콘 모두 클립보드에 저장
  2. 클립보드에 있는 이모티콘 화면에 붙여넣기
  3. 화면에 있는 이모티콘 하나 삭제

클립보드에 이모티콘이 하나라도 있어야 2번 작업 가능

화면에 이모티콘이 하나라도 있어야 3번 작업 가능

1번 작업은 언제나 수행 가능

2번 작업은 화면에 있는 이모티콘 + 클립보드 이모티콘이 목표(만들어야 할 이모티콘 수)이하여야 한다.

3번 작업은 화면에 있는 이모티콘 - 1이 0이상이어야 한다. (목표 이모티콘 최소 수가 2이기에 1이상이어도 상관 없다.)

각 작업은 1초로 동일한 시간이 걸리기에 BFS로 해결한다.

  • queue에는 <화면에 있는 이모티콘 수, 클립보드에 있는 이모티콘 수>가 저
  • 중복되지 않도록 dist라는 배열에 [화면][클립보드] 첨자를 이용해 시간을 저장한다.

1 Try

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <queue>
#include <tuple>
using namespace std;
queue<pair<int, int>> q;
int dist[1001][1001];
int main() {
	int n; cin >> n;
	q.push({ 1, 0 });
	while (!q.empty()) {
		int s, c;
		tie(s, c) = q.front();
		q.pop();
		if (dist[s][s] == 0) { // 화면에 있는 이모티콘 클립보드에 복사
			dist[s][s] = dist[s][c] + 1;
			q.push({ s, s });
		}
		if (s+c <= n && dist[s+c][c] == 0) { // 클립보드 화면에 붙여넣기
			dist[s + c][c] = dist[s][c] + 1;
			q.push({ s + c, c });
		}
		if (s - 1 >= 0 && dist[s - 1][c] == 0) { // 화면에 있는 이모티콘 -1
			dist[s - 1][c] = dist[s][c] + 1;
			q.push({ s - 1, c });
		}
	}
	int ans = 1e9;
	for (int i = 0; i <= n; ++i) { // 최솟값 찾기
		if (ans > dist[n][i] && dist[n][i] != 0) ans = dist[n][i];
	}
	cout << ans << "\n";
	return 0;
}
Algorithm