[BOJ/백준] 9019 DSLR

# # # 9019 DSLR 
# # # 레지스터 0이상 10000미만 십진수 저장
# # # n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4
# # # D는 n을 두배로 바꾼다. 결과값이 9999보다 큰 경우는 1만으로 나눈 값 (2n mod 10000)
# # # S : n에서 1을 뺀값 n이 0이면 9999로 대신 저장
# # # L : n을 각자리숫를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다.  d2, d3, d4, d1
# # # R : n을 오른쪽으로 회전 
import collections

def DSLR(num):
    D_num = num *2
    if D_num > 9999:
        D_num = D_num%10000
    S_num = num -1
    if not num:
        S_num = 9999
    L_num = (num*10)%10000 + num//1000
    R_num = num//10 + num%10*1000
    return [D_num,S_num,L_num,R_num]



T = int(input())
DSLR_IND = ['D','S','L','R']
for tc in range(T):
    A,B = list(map(int,input().split()))
    deque = collections.deque()
    deque.append((A,''))
    dp = [0]*10000
    dp[A] = 1
    flag = False
    while deque:
        num,result = deque.popleft()
        if num == B:
            break
        temp = DSLR(num)
        for ind in range(4):
            if not dp[temp[ind]]:
                dp[temp[ind]] = 1
                if temp[ind] == B:
                    result = result + DSLR_IND[ind]
                    flag = True
                    break
                deque.append((temp[ind],result+DSLR_IND[ind]))
        if flag:
            break
    print(result)

이 문제에서 어려웠던 점은 2가지였다.

첫번째는 시간초과의 압박이다. 스트링과 list의 특성을 이용해 L,R을 쉽게 구현을 할려고 했는데, str과 list를 이용해 L,R을 구현하는 순간 시간초과가 계속됬다.

두번째는 L,R의 제대로 된 이해였다.

문제를 처음봤을때 12가 있으면 이게 L이면 21이 되고 R이면 21이 되는줄 알았다. 이렇게 구현을 해놨었는데, 계속 틀렸습니다가 나와서 문제를 찬찬히 읽어보니 이 문제에서는 무조건 4자리로 강제가 되던것이다.

 

12가 그냥 12가 아닌 0012인 상태인것이다. 그래서 L을 하면 0120이 되는것이고 R을 하면 2001인 것이다. 이부분을 조심해줘서 풀면 되는 것이었다.

이 문제는 modular를 이용해 L,R을 구현해주면 된다.

L은 원래 Number에서 10배를 해주고 10000으로 나머지를 구한뒤, 제일 첫번째 숫자의 몫을 구하기 위해 Number의 1000으로 나눈 몫을 더해주면 된다.

R은 원래 Number를 10으로 나눈 몫을 구하고, 나머지에는 1000을 곱해서 더해주면 된다.

 

 

그리고 bfs를 이용해서 풀때, 목표값인 B와 비교를 해주는 것을 for문 밖 popleft를 한 바로 뒤에 나뒀더니, 의미없는 반복문이 더 진행이 되었기 때문에, for문 안에 두어서 바로바로 비교한뒤 flag를 두어서, 바로 결과가 출력되게 만들어줬다.