[백준]16397번: 탈출
탈출
문제
홍익이는 홍익대학교 프로그래밍 경진대회의 출제진이다. 홍익이는 새벽에 문제를 만들던 도중 뒤통수에 느껴지는 고통과 함께 정신을 잃었다.
홍익이는 좁은 방에서 눈을 떴다. 주변을 살펴보니 벽면에는 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
1 7 10
예제 출력 1
7
버튼을 A A A B A A A 순서로 누르면
1 -> 2 -> 3 -> 4 -> 7 -> 8 -> 9 -> 10 순서로 숫자가 변한다.
예제 입력 2
7142 10 7569
예제 출력 2
3
예제 입력 3
7142 1 7569
예제 출력 3
ANG
예제 입력 4
63429 99999 231
예제 출력 4
ANG
문제 해석
옛날에 DSLR이라는 문제를 풀어봤었다. D인 경우 어떠한 연산을 하고 S, L, R에 따라 각기 다른 연산을 하면서 정답을 찾아내는 최소의 알파벳을 찾아내는 건데 이 문제도 비슷하다. A, B에 따른 각 다른 연산이 존재하고, 어떠한 답에 도달했을 때 최소 경로를 찾는 것이다. bfs를 이용하여 queue에 이런 각기 다른 경우들을 append 해주면서 답을 찾아내는 것인데, 유의해야 할 것은 visited 리스트를 이용하여 특정 수를 방문을 한다면 그 수는 다시 queue에 넣지 않게끔 방문 처리를 해줘야 한다. 안 그러면 같은 수들이 계속해서 들어가면서 같은 연산이 2 ^ n 번 만큼 반복이 되기 때문이다.
풀이
- 만약 N == G (입력 받은 수와 도달해야 하는 수가 같은 경우)
- 1번도 연산 안해도 도달해야 하는 수와 같기 때문에 0을 출력해주고 시스템을 종료한다.
- bfs 함수 선언
- flag = 0 (while문을 다 돌았는데 수에 도달하지 못하는 경우를 위해)
- 만약 count == T (최대 계산 가능 횟수)
- continue (가장 먼저 최대 도달 횟수에 그 다음에 정답이 나올 수도 있기 때문에 break가 아닌 continue를 해준다.)
- A인 경우
- N_A = N + 1 해줌
- 만약 N_A == G (G라는 수에 도달한다면 break를 하는데 최소 비용이기 때문에 가장 먼저 계산이 된 결과가 최소 비용이다.)
- print(count + 1)
- flag = 1 (while문 다 돌기 전에 수를 찾아서 ANG을 출력 안하기 위해 flag를 1로 바꿔준다.)
- break
- 만약 N_A != 99999 (99999가 되면 그 다음 연산 결과들은 무조건 넘어가기 때문에 queue에 appen 해줄 필요가 없음)
- queue에 append (N_A, count + 1)
- 만약 N != 0
- N_B = N * 2
- 만약 N_B > 99999
- continue
- 그게 아니라면?
- list_N_B = list(N_B)
- list_N_B[0] -= 1
- 루프
- a += list_N_B[i] * (10 ** (len(list_N_B) - 1 - i))
- 자릿수를 이용해서 10의 제곱만큼 각 자리에 맞게 곱해주면서 a에 더해준다.
- 만약 a == G
- print(count + 1)
- flag = 1
- break
- queue에 append (a, count + 1)
- 만약 N_B > 99999
- N_B = N * 2
- 만약 flag == 0:
- while문을 다 돌았는데도 수를 못 찾은 것이기 때문에 ANG을 출력해준다.
import sys
from collections import deque
N, T, G = map(int, sys.stdin.readline().split())
queue = deque()
queue.append((N, 0))
visit = [0] * 100000
if N == G:
print("0")
exit()
def bfs():
N_A = 0
N_B = 0
while queue:
flag = 0
N, count = queue.popleft()
if count == T:
continue
N_A = N + 1
if N_A == G:
print(count + 1)
flag = 1
break
if N_A < 100000 and visit[N_A] == 0:
visit[N_A] = 1
queue.append((N_A, count + 1))
if N != 0:
N_B = N * 2
if N_B > 99999:
continue
else:
list_N_B = list(str(N_B))
c = int(list_N_B[0])
c -= 1
list_N_B[0] = str(c)
a = 0
for i in range(len(list_N_B)):
a += int(list_N_B[i]) * (10 ** (len(list_N_B) - 1 - i))
# a = str(N_B)
# a = str(int(a[0]) - 1) + a[1:]
if int(a) == G:
print(count + 1)
flag = 1
break
if visit[int(a)] == 0:
queue.append((int(a), count + 1))
visit[int(a)] = 1
if flag == 0:
print("ANG")
bfs()
고찰
- 코드를 다 짜고 나서 계속 21퍼센트에서 틀리기에 계속 고민을 했다.
- 한가지 예외 처리를 안해준 것이, 입력 받은 수와 도달 해야 하는 수가 같은 경우이다.
- 이 경우는 한번의 연산도 없이 도달해야 하는 수에 도달했기 때문에 0을 출력을 해줘야한다.
- 그리고 맨 앞자리에서 1을 빼주는 경우인데
- 필자는 리스트를 이용하여 0번지의 수를 1빼주고 자릿수 만큼 10의 n승을 곱해줘서 숫자를 만들었는데
- 파이썬의 slicing 을 이용하면 주석처리한 코드처럼 쉽게 해결할 수 있다.
댓글남기기