반응형
14226번: 이모티콘
영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만
www.acmicpc.net
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 34 35 36 37 38 39 40 41 42 43 44 | // https://yabmoons.tistory.com/74 #include <iostream> #include <queue> #define pii pair<int, int> using namespace std; int n, cnt; bool visited[1001][1001]; queue<pii> q; void bfs(int i, int j) { visited[i][j] = 1; q.push({ i,j }); while (!q.empty()) { int size = q.size(); cnt++; while (size--) { int screen = q.front().first; int clipboard = q.front().second; q.pop(); if (screen == n) { // 화면 이모티콘 n개 되면 종료 cout << cnt; return; } // 1. 복사 if (!visited[screen][screen]) { visited[screen][screen] =1; q.push({ screen, screen }); } // 2. 붙여넣기 if (screen + clipboard <= 1000 && !visited[screen + clipboard][clipboard]) { visited[screen + clipboard][clipboard] =1; q.push({ screen + clipboard, clipboard }); } // 3. 삭제 if (screen > 0 && !visited[screen - 1][clipboard]) { visited[screen - 1][clipboard] = 1; q.push({ screen - 1, clipboard }); } } } } int main() { cin >> n; bfs(1, 1); } | cs |
반응형