-
백준 14226 C++알고리즘/백준(BOJ) 2022. 9. 27. 13:51반응형
https://www.acmicpc.net/problem/14226
문제
영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다.
영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.
- 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
- 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
- 화면에 있는 이모티콘 중 하나를 삭제한다.
모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다. 또한, 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없다. 화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다.
영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 S (2 ≤ S ≤ 1000) 가 주어진다.
출력
첫째 줄에 이모티콘을 S개 만들기 위해 필요한 시간의 최솟값을 출력한다.
접근법
- 각 차례가 끝날때마다, 복사할지 / 붙여넣기 할지 / 삭제할지를 선택해야 한다.
- 그래서, 한 단계마다 3가지의 가지치기가 가능해지므로, BFS 방식으로 접근이 가능하다.
- 대신, 방문했다는 노드를 표시할때, 상태를 기록해주는 것이 중요한데, (예를들어, visited[ ] [ ] 형식) 여기서는 복사한 상태까지 기록해주어, 2차원의 visited를 사용해주었습니다.
ps. 1차원의 visited만을 사용하여 처음에 접근하였지만, 각 차례에서, 현재 시간 m 이고, 클립보드 상태가 p ,q 로 서로 다를 수 있으므로, visited를 2차원으로 접근하였습니다.
#include <iostream> #include <string> #include <queue> #include <algorithm> using namespace std; struct Command { int Time; int ClipCount; Command(int _t, int _c) : Time(_t), ClipCount(_c){} }; void solve(int T, vector<vector<int>>& visited , Command& _command) { queue<Command> queueCommand; queueCommand.push(_command); while(!queueCommand.empty()) { _command = queueCommand.front(); queueCommand.pop(); int now = _command.Time; int clip = _command.ClipCount; /* RETURN */ if(now == T) { cout << visited[now][clip] - 1 << endl; break; } /* COPY */ int nextClip = now; if(visited[now][nextClip] == 0) { queueCommand.push(Command(now, nextClip)); visited[now][nextClip] = visited[now][clip] + 1; } /* PASTE */ if(now + clip <= T) { int new_clip = now + clip; if(visited[new_clip][clip] == 0) { queueCommand.push(Command(new_clip, clip)); visited[new_clip][clip] = visited[now][clip] + 1; } } /* Delete */ if(now > 0) { if(visited[now - 1][clip] == 0) { queueCommand.push(Command(now - 1, clip)); visited[now - 1][clip] = visited[now][clip] + 1; } } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); /*----------------- INPUT -------------------*/ int T; cin >> T; vector<vector<int>> s; s.resize(1000 + 1); for(int i = 0; i < 1000 + 1; i++) { s[i].resize(1000 + 1); } /*----------------- SOLVE -------------------*/ Command c(1, 0); s[1][0] = 1; solve(T, s, c); return 0; }
반응형'알고리즘 > 백준(BOJ)' 카테고리의 다른 글
백준 1261 C++ (0) 2022.10.20 백준 16935 C++ (0) 2022.10.04 백준 10845 C++ (0) 2022.09.27 백준 ABCDE C++ (0) 2022.09.27 백준 16194 c++ (0) 2021.10.14