[백준 14226] 이모티콘 (C++)

문제 링크: https://www.acmicpc.net/problem/14226

14226번: 이모티콘

1. 주의할 점

- BFS를 통해 해결하며, 현재 이모티콘의 길이만큼만 비교하는 배열을 사용하면 틀린 답이 나온다(ex. 872 -> 22가 나와야 한다)

 

2. 구현

- Check[][]배열을 통해 현재 이모티콘의 길이, 현재 클립보드에 저장되어있는 길이를 비교한다

- 입력으로 1이 주어지는 경우 바로 0을 출력한다

- 현재 이모티콘의 길이가 구하고자 하는 값과 같다면 Result와 비교하여 갱신한다

- Result를 갱신하는 If문을 제외하고, 첫 번째 If문은 현재 화면에 나타난 이모티콘 1개를 삭제하는 경우(문제 3번)

- 두 번째 If문은 현재 클립보드에 저장되어 있는 이모티콘의 길이만큼 추가하는 경우(문제 2번)

- 마지막 If문은 클립보드에 현재 이모티콘의 길이만큼 복사하는 경우(문제 1번)

 

#define MAX 987654321
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
struct info {
	int len, val, copy;
};
info tmp;
int check[1001][1001], num;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	for (int i = 1; i <= 1000; i++)
		for(int j=0;j<=1000;j++)
			check[i][j] = MAX;
	cin >> num;
	int result = MAX;
	if (num == 1) cout << 0;	
	else {
		queue<info> q;
		tmp.len = 1;
		tmp.val = 0;
		tmp.copy = 0;
		check[1][0] = 0;
		q.push(tmp);
		while (!q.empty()) {
			int cl = q.front().len;
			int cv = q.front().val;
			int cp = q.front().copy;
			q.pop();
			if (cl == num) 
				result = min(result, cv);			
			if (cl - 1 > 0 && check[cl - 1][cp] > cv + 1) {
				check[cl - 1][cp] = cv + 1;
				tmp.len = cl - 1;
				tmp.val = cv + 1;
				tmp.copy = cp;
				q.push(tmp);
			}
			if (cp>0 && cp+cl<=1000 && check[cp+cl][cp]>cv+1) {
				check[cp + cl][cp] = cv + 1;
				tmp.len = cp + cl;
				tmp.val = cv + 1;
				tmp.copy = cp;
				q.push(tmp);
			}
			if (check[cl][cl]>cv+1 && cv + 1 < result) {
				tmp.copy = cl;
				tmp.val = cv + 1;
				tmp.len = cl;
				q.push(tmp);
			}
		}
		cout << result;
	}
	return 0;
}