탈출
문제
홍익이는 홍익대학교 프로그래밍 경진대회의 출제진이다. 홍익이는 새벽에 문제를 만들던 도중 뒤통수에 느껴지는 고통과 함께 정신을 잃었다.
홍익이는 좁은 방에서 눈을 떴다. 주변을 살펴보니 벽면에는 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는 탈출을 위해 똑같이 만들어야 하는 수를 뜻한다.
출력
첫 번째 줄에 N (0 ≤ N ≤ 99,999), T (1 ≤ T ≤ 99,999), G (0 ≤ G ≤ 99,999)가 공백 하나를 사이에 두고 주어진다.
각각 N은 LED로 표현된 수, T는 버튼을 누를 수 있는 최대 횟수, G는 탈출을 위해 똑같이 만들어야 하는 수를 뜻한다.
예제 입력 1
1
1 7 10
예제 출력 1
1
7
예제 입력 2
1
7142 10 7569
예제 출력 2
1
3
예제 입력 3
1
7142 1 7569
예제 출력 3
1
ANG
예제 입력 4
1
63429 99999 231
예제 출력 4
1
ANG
풀이 과정
N을 G로 만드는 최소 버튼 조작 횟수를 계산하는 문제이므로 BFS를 사용해서 풀었다.
BFS 함수에서 현재 숫자와 버튼을 누른 횟수를 큐에 저장하고, A 버튼을 눌렀을 때는 현재 숫자에 1을 더한 결과를 큐에 추가하고, B 버튼을 눌렀을 때는 B_number 함수를 사용해서 현재 숫자를 2배로 만들고 가장 큰 자릿수의 숫자에서 1을 뺀 결과를 큐에 추가한 후에 방문 처리를 함으로써 같은 숫자에 대한 중복 계산을 방지했다.
limit 변수를 설정해서 한계 숫자를 설정했다.
처음에 문제를 봤을 때 B버튼을 눌렀을 때 숫자 처리를 BFS 함수 내에서 하려고 했으나 조건문이 너무 복잡해지는 거 같아서 따로 함수로 처리했다!