[백준 9019번] 파이썬 - DSLR

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

9019번: DSLR

 

 

# 조건

• 네 개의 명령어 D, S, L, R 이용하는 간단한 계산기
• 레지스터에는 0 이상 10,000 미만의 십진수를 저장
• n의 네 자릿수를 d1, d2, d3, d4라고 하자
  1. D는 n을 두 배로 바꾼다. 결과 값이 9999보다 큰 경우 10000으로 나눈 나머지를 취하고 그 결과 값 (2n mod 10000)을 레지스터에 저장
  2. S는 n에서 1을 뺀 결과 n-1을 레지스터에 저장
  3. L은 n의 각 자릿수를 왼편으로 회전시켜 레지스터에 저장
  4. R은 n의 각 자릿수를 오른편으로 회전시켜 레지스터에 저장
• 서로 다른 두 정수 A와 B에 대해 A를 B로 바꾸는 최소한의 명령어를 생성

 

# 접근 방법

• A에 대해 각 연산을 수행한 결과를 저장해준다.
• stack이 아닌 q를 이용하여 가장 최소한의 연산을 이용한 것을 구해준다.
• 방문 기록 배열 VISITED는 최댓값이 10000이므로 10000의 길이로 해준다.
• 예
  • 1234에 대해 DSLR 연산의 결과를 VISITED에 기록해준다.
  • 이 때, 이미 기록이 되어있다면 지금 하고 있는 연산은 최소가 아니기 때문에 걸러줄 수 있다.
• 연산 기호를 계속 붙여주며 구해준다.
• 왼쪽, 오른쪽 시프트 해주는 것만 잘 생각하면 쉬웠던 문제인 듯!

 

# PYPY 통과

import sys  
from collections import deque  
  
for _ in range(int(sys.stdin.readline())):  
    A, B = map(int, sys.stdin.readline().split())  
    q = deque()  
    visit = [0] * 10000  
    q.append((A, ''))  
    visit[A] = 1  
    while q:  
        n, operation = q.popleft()  
        if n == B:  
            print(operation)  
            break  
  
        # D 연산  
        D_num = (2 * n) % 10000  
        if visit[D_num] == 0:  
            q.append((D_num, operation + 'D'))  
            visit[D_num] = 1  
  
        # S 연산  
        # 0보다 작아지는 경우 9999로 반환  
        S_num = n - 1 if n != 0 else 9999  
        if visit[S_num] == 0:  
            q.append((S_num, operation + 'S'))  
            visit[S_num] = 1  
  
        # L 연산  
        # 10을 곱한 값의 나머지 + 몫  
        L_num = 10 * (n % 1000) + n // 1000  
        if visit[L_num] == 0:  
            q.append((L_num, operation + 'L'))  
            visit[L_num] = 1  
  
        # R 연산  
        # 10으로 나눈 나머지 * 1000 + 몫  
        R_num = 1000 * (n % 10) + n // 10  
        if visit[R_num] == 0:  
            q.append((R_num, operation + 'R'))  
            visit[R_num] = 1