문제
홍익이는 홍익대학교 프로그래밍 경진대회의 출제진이다. 홍익이는 새벽에 문제를 만들던 도중 뒤통수에 느껴지는 고통과 함께 정신을 잃었다.
홍익이는 좁은 방에서 눈을 떴다. 주변을 살펴보니 벽면에는 LED로 된 다섯 자리 십진수 N이, 그 옆에 T, G라는 알파벳과 함께 또 다른 정수 두 개가 쓰여 있었고, 벽 앞에는 버튼 A, B 두 개가 있었다.
버튼을 이리저리 눌러보던 똑똑한 홍익이는 어떻게 해야 방을 탈출할 수 있을지 금방 눈치챘다.
버튼과 수에 대해 홍익이가 알아낸 것은 다음과 같다.
- 버튼 A를 누르면 N이 1 증가한다.
- 버튼 B를 누르면 N에 2가 곱해진 뒤, 0이 아닌 가장 높은 자릿수의 숫자가 1 줄어든다. 예를 들어 123→146으로, 5→0으로, 3→5로 변한다. 단, N이 0이면 버튼 B를 눌러도 수가 변하지 않는다.
- LED가 다섯 자리까지밖에 없기 때문에 N이 99,999를 넘어가는 순간 탈출에 실패하게 된다.
- 버튼 B를 눌러 N에 2를 곱한 순간 수가 99,999를 넘어간다면, 높은 자릿수의 수를 1 낮췄을때 99,999를 넘지 않는다고 해도 탈출에 실패하게 된다.
또한 홍익이는 최대 T회 버튼을 누를 수 있고, 그 횟수 안에 LED로 표현된 N을 G와 같게 만들어야 탈출할 수 있다는 사실을 알아냈다.
똑똑한 홍익이는 이와중에 자존심이 발동해 버튼 누르는 횟수를 최소로 하여 방을 탈출하기로 했다.
홍익이의 방 탈출을 기원하며, 탈출에 필요한 최소의 버튼 횟수를 구하자.
입력
첫 번째 줄에 N (0 ≤ N ≤ 99,999), T (1 ≤ T ≤ 99,999), G (0 ≤ G ≤ 99,999)가 공백 하나를 사이에 두고 주어진다.
각각 N은 LED로 표현된 수, T는 버튼을 누를 수 있는 최대 횟수, G는 탈출을 위해 똑같이 만들어야 하는 수를 뜻한다.
출력
첫 번째 줄에 탈출에 필요한 최소의 버튼 횟수를 출력한다.
만약 탈출할 수 없다면 “ANG”을 따옴표 없이 출력한다.
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
45
|
#include <iostream>
#include <queue>
using namespace std;
string bfs() {
queue<pair<int, int>> myQueue; //숫자, 버튼누른횟수
bool visited[100000] = {false,};
int range[] = {1, 10, 100, 1000, 10000, 100000};
int n, t, g;
cin >> n >> t >> g;
visited[n] = true;
myQueue.push({n, 0});
while (!myQueue.empty()) {
int num = myQueue.front().first, btn = myQueue.front().second;
myQueue.pop();
if (num == g)
return to_string(btn);
if (btn == t) //버튼은 최대 t번 누를 수 있음
continue;
if (num + 1 <= 99999 && !visited[num + 1]) { //99999이하
visited[num + 1] = true;
myQueue.push({num + 1, btn + 1});
} //버튼 A
if (num * 2 <= 99999) { //1 낮추기 전의 수도 99999이하
for (int i = 0; i < 6; i++)
if (range[i] <= num * 2 && num * 2 < range[i + 1]) {
num = num * 2 - range[i];
break;
}
if (!visited[num]) {
visited[num] = true;
myQueue.push({num, btn + 1});
}
}
} //버튼 B
return "ANG";
}
int main() {
cout << bfs() << '\n';
return 0;
}
|
cs |
버튼을 누를 수 있는 횟수에 제한이 있다는 점과 버튼 B를 눌렀을 때 1을 낮추기 전의 숫자도 99999를 넘으면 안된다는
점만 주의해서 풀면 된다.
'백준 온라인 저지 (BOJ) 문제풀이' 카테고리의 다른 글
백준 온라인 저지 20937 떡국 (0) | 2021.03.01 |
---|---|
백준 온라인 저지 2143 두 배열의 합 (0) | 2021.02.26 |
백준 온라인 저지 20951 유아와 곰두리차 (0) | 2021.02.23 |
백준 온라인 저지 1025 제곱수 찾기 (0) | 2021.02.20 |
백준 온라인 저지 17836 공주님을 구해라! (0) | 2021.02.15 |