백준 14226 - 이모티콘

문제 설명

영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다.

영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.

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

모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다. 또한, 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없다. 화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다.

영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 3가지 연산을 통해 N개의 이모티콘을 입력하는 최소 시간을 구하는 것이다.

• 현재 화면 복사
• 현재 클립보드 붙여넣기
• 현재 화면에서 하나 지우기

세 연산 모두 1의 시간이 든다.

 

해당 문제를 처음 보면 bfs 혹은 dp 등으로 풀 수 있을 거라고 생각이 들 것이다.

 dp로 접근하려 했더니 연속된 붙여 넣기나 번갈아가며 복사하고 붙여 넣는 등의 처리가 쉽지 않았다.

그래서 bfs를 통해 접근해 봤다.

 

1개의 이모티콘이 화면에 쓰여있는 상태로 시작한다.

따라서 이모티콘 1개를 쓰는 시간은 0이다.

이를 시작으로 복사할 때, 붙여 넣을 때, 지울 때를 큐에 넣어 분기를 늘려가면 된다.

이때, 모든 연산을 무조건 실행할 수 있지 않다.

 

우선, 복사의 경우 이미 복사한 수의 경우에는 중복으로 처리할 필요가 없다.

예를 들어, 1개에서 복사하여 2개를 만들고 거기서 1개를 지우면 다시 1개가 된다.

이 경우 똑같이 복사 연산을 하면 무한 루프를 돌게 된다.

//복사
if (!visit[screen])
{
    visit[screen] = 1;
    q.push({ screen, screen, time + 1 });
}

 

붙여 넣기의 경우 현재 클립보드에 저장된 길이와 화면의 길이가 합쳐지게 된다.

따라서, 이 길이가 특정 길이 이상이 된다면 최소 시간을 보장하지 않는다.

N을 넘게 되면 줄어들 수 있는 연산은 1을 줄이는 연산밖에 없기에 최소 시간을 구할 확률이 높지 않다.

이는 적절히 조절하면 되는데 N으로 설정해도 AC를 받을 수 있다.

만약 N+1을 N/x 보다 빠른 시간에 만들 수 있다면 N을 넘겨서도 최소 시간을 만들 수 있지만 N+1을 N/x보다 빠른 시간에 만드는 것은 불가능하다.

1을 늘릴 수 있는 경우는 최초 상태에서 아무것도 복사하지 않은 상태에서 계속하여 붙여 넣어야 하며 꼭 1이 아니더라도 +n을 늘리는 경우도 복사하여 곱으로 늘리는 경우보다 느릴 것이며 N을 넘긴 이후에도 1씩 계속 빼주어야 하기 때문이다.

//붙여넣기
if (screen + clip <= N)
{
    q.push({ screen + clip, clip, time + 1 });
}

 

마지막으로 1을 빼는 연산을 추가하여 Bfs를 진행하면 답을 구할 수 있다.

//지우기
if (screen - 1 >= 0)
{
    q.push({ screen - 1, clip, time + 1 });
}

 

 

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
int N;
const int MAX = 1001;
vector<int> visited(MAX, INT_MAX);

int main() 
{
    INPUT_OPTIMIZE;

    cin >> N;

	vector<bool> visit(MAX, false);

	queue<tuple<int, int, int>> q;
	q.push({ 1,0, 0 });

	while (!q.empty()) 
	{
		auto [screen, clip, time] = q.front();
		q.pop();

		if (screen == N)
		{
			cout << time;
			return 0;
		}

		//복사
		if (!visit[screen])
		{
			visit[screen] = 1;
			q.push({ screen, screen, time + 1 });
		}

		//붙여넣기
		if (screen + clip <= N)
		{
			q.push({ screen + clip, clip, time + 1 });
		}

		//지우기
		if (screen - 1 >= 0)
		{
			q.push({ screen - 1, clip, time + 1 });
		}
	}

    return 0;
}

---