[백준 9019번] DSLR (Python/파이썬)

https://www.acmicpc.net/problem/9019

9019번: DSLR

문제를 처음 보면 그래프 문제라고는 생각하기 힘들수도 있지만, 범위를 보면 하나씩 다 채울만 하겠다 라는 생각이 든다.

숫자가 0부터 9999까지 밖에 없으므로 이전에 했던 과정을 저장하면서 4가지의 과정을 노가다로 다 저장하면 된다.

처음에는 "" 빈 문자열이고 숫자를 받으면 그에대해서 D, S, L, R을 각각 실행한다. 그럼 실행한 숫자까지 필요한 과정으로 각각 D, S, L, R이 저장되어 있을것이다. "D", "S", "L", "R"

D,S,L,R로 만든 숫자들로 또 DSLR을 수행한다. 위의 과정을 반복하면서 만들어야하는 숫자의 인덱스가 "" 빈문자열이 아니면 반복을 종료한다.

코드는 다음과 같다.

 

import sys
from collections import deque
input = sys.stdin.readline
T = int(input())
for _ in range(T):
  A, B = map(int,input().split())
  save = [""]*10000
  queue = deque([])
  queue.append((A,""))
  while True:
    (tmp, com) = queue.popleft()
    D = (tmp*2) % 10000
    if save[D] == "":
      save[D] = com + "D"
      queue.append((D,save[D]))

    if not tmp:
      S = 9999
    else:
      S = (tmp - 1)
    if save[S] == "":
      save[S] = com + "S"
      queue.append((S,save[S]))

    x = tmp * 10
    y = tmp*10//10000
    L = (x - 9999*y)
    if save[L] == "":
      save[L] = com + "L"
      queue.append((L,save[L]))
    
    x = tmp // 10
    y = tmp % 10
    R = x + 1000*y
    if save[R] == "":
      save[R] = com + "R"
      queue.append((R,save[R]))
    
    if save[B] != "":
      print(save[B])
      break

 

python으로 했는데 시간초과 나서 pypy3로 했더니 통과되었다.

기본 제한시간도 6초인걸 보면 원래 좀 오래걸리는 문제다.