탈출

문제 분석

이전에 몇번 풀어봤던 1로 만들기와 비슷한 유형의 DP문제이다.

n,t,g가 주어질 때, t번 안에 n을 g로 바꿀 수 있는지, 바꿀 수 있다면 몇 회만에 변환되는지 출력하는 문제이다.

1로 만들기 같은 경우에는 2와 3으로 나눌 수도 있고, 1을 뺄 수도 있다. 이 문제에서는 버튼 두개가 있고, 1을 증가시키거나, 2를 곱한 후 0이 아닌 가장 높은 자리수의 숫자를 1 감소시키는 방법 두가지가 있다는 차이점이 존재한다.

또한, 이 문제에서는 버튼 A를 누르냐 B를 누르냐에 따라, 숫자가 증가할 수도, 감소할 수도 있기 때문에 이 점이 더 까다로웠던 것 같다. 만약에 56에서 버튼 B를 누르면 112가 되고, 최고자리 수에서 1을 감소시키면 12가 되면서 숫자가 감소한다.

수가 항상 감소하는 1로 만들기와는 달리, 이 문제는 증가할 수도 감소할 수도 있다. 그래서 BFS를 함께 사용해 주었다. DFS를 이용하면, 최소 횟수가 아닌 횟수가 걸릴 수도 있고, BFS를 사용하지 않으면 숫자의 제한범위 까지 항상 모두 탐색하는 상황이 발생할 것 같았다.

BFS를 이용해 조건을 만족하는 숫자들을 dp에 저장해 나가며 BFS로 탐색했다. dp에는 각 숫자까지 도달하는데 누른 버튼의 최소 횟수를 저장했다. 그러다가 g와 같은 숫자가 등장하면, while문을 탈출한 후 해당 숫자의 dp값을 출력한다. 만약에 while문을 break없이 point리스트의 원소의 개수가 0이 되어끝냈다면, ANG를 출력한다.


CODE

import sys
read=sys.stdin.readline
from collections import deque

n,t,g=map(int,read().split())

dp=list(-1 for _ in range(100_000))
dp[n]=0

point=deque([n])

answer=-1 #flag 겸, 답을 저장하는 변수
#BFS
while point:
    a=point.popleft()
    if a == g:
        answer=dp[a]
        break
    if a ==0 and dp[1]>dp[0]+1:
        dp[1]=dp[0]+1
        point.append(1)
    else:
        if a*2<100_000:
            #가장 높은 자리수의 숫자를 1 감소시키는 작업
            tmp=str(a*2)
            if tmp[0]=='1': tmp=tmp[1:]
            else:
                tmp=str(int(tmp[0])-1)+tmp[1:]
            tmp=int(tmp)
            if dp[tmp]==-1 and tmp>=0:
                dp[tmp]=dp[a]+1
                point.append(tmp)
        if a+1<100_000:
            if dp[a+1]==-1:
                dp[a+1]=dp[a]+1
                point.append(a+1)

if answer==-1 or answer>t: print("ANG")
else: print(answer)


틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]