문제
문제접근
문제 이해
- 우리가 취할 수 있는 액션은 세 가지입니다.
- 화면의 이모티콘 개수는 그대로, 클립보드 개수는 화면의 이모티콘 개수로 변경.
- 화면의 이모티콘 개수는 기존 + 클립보드 개수로 변경, 클립보드 개수는 그대로.
- 화면의 이모티콘 개수는 기존 - 1로 변경, 클립보드 개수는 그대로.
- 모든 연산은 1초가 걸리고 최소시간을 구하는 문제이므로 BFS를 사용해서 풀 수 있습니다.
풀이 1
- 우리가 지금까지 알고있던 방법을 그대로 사용해봅시다.
- 화면의 이모티콘 개수
cnt
와 클립보드의 이모티콘 개수 clip
이 있습니다.
queue
를 만들고, 위 세 가지 액션을 그대로 적용해봅시다.
q.push({cnt, cnt})
→ 복사
q.push({cnt + clip, clip})
→ 붙혀넣기
q.push({cnt - 1, clip})
→ 하나 제거
- 이때
cnt + clip
과 cnt - 1
이 최대범위를 넘지 않도록 조건문을 잘 설정해주면 됩니다.
- 이 문제에서는 이전과 달리 따로 방문 여부를 체크하지 않습니다.
왜냐하면, 처음에 이모티콘 개수가 1
일 때, 복사하고 난 뒤 방문표시를 해버리면 1
은 이미 방문된 점이므로 조건문에 들어가지 않아 붙혀넣기가 불가능하기 때문입니다.
- 대신 이 문제에서는 복사 여부를 체크합니다.
왜냐하면, 복사는 cnt
의 값이 변하지 않고 방문 여부도 체크하지 않으므로 무한 loop를 일으킬 가능성이 있기 때문입니다.
풀이 2
- <풀이 1>에는 단점이 있습니다.
- 가장 큰 단점은 너무 많은 검사를 하게된다는 점입니다.
- 원인은 바로 방문 여부 비체크 때문입니다. 자칫 잘못하면 TLE나 MLE를 유발할 수 있습니다.
- 방문 여부를 체크하는 이유는 중복검사를 회피하기 위해서입니다.
하지만, 방문 여부를 체크하지 않으니 중복검사를 피할 길이 없게됩니다.
- 두 번째 단점은 이 문제가 엄청나게 많은 간선이 존재하는 그래프와 같다는 점입니다.
- 예를 들어, 이모티콘 10개를 만들기 위해서는 수많은 경우의 수가 있습니다.
1
을 복사하고 10번 붙혀넣기 해서 만드는 경우도 있고
1
을 복사하고 붙혀넣고 또 복사하고 붙혀넣는 것을 반복해서 만드는 경우도 있습니다.
- 즉, 이 문제는 N개의 이모티콘(정점)에 대해 N×(N−1)/2개 간선이 있는 그래프와 같습니다.
- 따라서 위 두 가지 단점을 모두 극복하기 위해서 이모티콘의 개수 표현 방법을 바꿉니다.
- 기존 → 개수로 이뤄진 1차원 배열
- 변경 → 개수, 클립보드 개수로 이뤄진 2차원 배열
time[][]
이라는 행이 화면상의 이모티콘 개수, 열이 클립보드의 이모티콘 개수인 2차원 배열을 만듭니다.
- 만일
time[cnt] [cnt] == -1
이면 아직 방문하지 않은(?) 이모티콘 개수이므로 복사가 가능한 상태입니다.
- 만일
time[cnt + clip] [clip] == -1
이면 붙혀넣기가 가능한 상태입니다.
- 만일
time[cnt - 1] [clip] == -1
이면 하나 지우기가 가능한 상태입니다.
코드
풀이 1
#include <iostream>
#include <queue>
#include <tuple>
#define MAX 1001
using namespace std;
int S, copied[MAX];
int solve() {
queue<tuple<int, int, int>> q;
q.push({1, 0, 0});
while (!q.empty()) {
int cnt, clip, time; tie(cnt, clip, time) = q.front();
if (cnt == S) return time;
q.pop();
int nTime = time + 1;
if (cnt > 2) q.push({cnt - 1, clip, nTime});
if (clip != 0 && cnt + clip < MAX) q.push({cnt + clip, clip, nTime});
if (!copied[cnt]) q.push({cnt, cnt, nTime}), copied[cnt] = true;
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> S;
cout << solve();
}
풀이 2
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int S, time[1001][1001];
int solve() {
queue<pair<int, int>> q;
q.push({1, 0});
time[1][0] = 0;
while(!q.empty()) {
int now = q.front().first, clip = q.front().second;
q.pop();
int next1 = now + clip, next2 = now - 1;
if (time[now][now] == -1)
time[now][now] = time[now][clip] + 1, q.push({now, now});
if (next1 <= S && time[next1][clip] == -1)
time[next1][clip] = time[now][clip] + 1, q.push({next1, clip});
if (next2 >= 0 && time[next2][clip] == -1)
time[next2][clip] = time[now][clip] + 1, q.push({next2, clip});
}
int ans = -1;
for (int i = 1; i <= S; ++i)
if (ans == -1 || ans > time[S][i]) ans = time[S][i];
return ans;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> S;
memset(time, -1, sizeof(time));
cout << solve();
}
결과