https://www.acmicpc.net/problem/9019
9019번: DSLR네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에www.acmicpc.net
간단한? dfs문제
처음에는 L,R을 string으로 구현하려 했었지만,
생각해보니 그냥 10으로 나누거나(몫) 곱해주고, 끝자리나 첫자리만 따로 처리해서 더해주면 된다.
파이썬은 느려서 pypy로 제출했다. 파이썬으로 푼 사람이 3명밖에없다!!
from collections import dequeimport sysinput=sys.stdin.readlinedef D(n:int):
rv=n<<1 if rv>9999: rv%=10000 return rvdef S(n:int): rv=n-1
if rv==-1: rv=9999 return rvdef L(n:int):
a,b=divmod(n,1000) #첫자리, 나머지3자리 rv=(b*10)+a #세지리 값 변경, 첫자리값넣기
return rvdef R(n:int): a,b=divmod(n,10) #나머지3자리, 끝자리 rv=b*1000+a #앞세자리
return rvdd={ 'D':D, 'S':S, 'L':L, 'R':R,}def bfs(start,end):
arr=[None for _ in range(10000)] arr[start]='' q=deque([start])
while q: now=q.popleft() for k,v in dd.items():
next= v(now) if 0<=next<10000 and arr[next]==None:
arr[next]=arr[now]+k q.append(next)
if next==end: print(arr[end])
return
for _ in range(int(input())): start,end=map(int,input().split())
bfs(start,end)