BOJ 9019 DSLR

LONGNEW·2021년 1월 24일
0

BOJ

목록 보기
94/333

https://www.acmicpc.net/problem/9019
시간 6초, 메모리 256MB
input :

  • T 개의 테스트 케이스
  • A B(A ≠ B)(A는 레지스터의 초기 값을 나타내고 B는 최종 값)(0 <= A, B < 10,000)

output :

  • 최소한의 명령어 나열을 출력한다. 가능한 명령어 나열이 여러가지면, 아무거나 출력

조건 :

  • n의 네 자릿수를 d1, d2, d3, d4
  • D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.
  • S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
  • L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.
  • R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.

최소한의 명령어 나을 출력하는데, 가능한 명령어 나열이 여러가지일 수도 있다고 한다. 이는 BFS를 나타내는 것이라고 보고 BFS를 이용했다.

처음에는 D, S 를 10000과 0으로 조건을 나눠서 풀었는데 이 경우에 valueerror가 발생했다. 다른 분들의 풀이를 보니 10000 으로 나머지를 구해서 푸시길래 나도 이와 동일하게 바꾸었다.

LR의 경우에는 숫자가 1일 때, 0001 / 0010 으로 만들어 주어야 한다. 이는 str의 zfill 을 이용해서 4자리 중 숫자보다 앞 칸이 비어 있다면 0으로 채우게 만든다.

import sys
from _collections import deque

t = int(sys.stdin.readline())

for i in range(t):
    a, b = map(int, sys.stdin.readline().split())
    dp = [-1] * 10001

    if len(str(a)) < 4:
        a = str(a).zfill(4)

    q = deque([(a, '')])
    dp[int(a)] = 1

    while q:
        now_str, command = q.popleft()
        if type(now_str) != str:
            now_str = str(now_str)
        now = int(now_str)

        if now == b:
            print(command)
            break

        next_num = (now * 2) % 10000
        next_str = str(next_num)
        if dp[next_num] == -1:

            if next_num < 1000:
                next_str = next_str.zfill(4)

            dp[next_num] = 1
            q.append((next_str, command + 'D'))

        next_num = (now - 1) % 10000
        next_str = str(next_num)
        if dp[next_num] == -1:

            if next_num < 1000:
                next_str = next_str.zfill(4)

            dp[next_num] = 1
            q.append((next_str, command + 'S'))

        next_str = now_str[1:] + now_str[0]
        next_num = int(next_str)
        if dp[next_num] == -1:
            dp[next_num] = 1
            q.append((next_str, command + 'L'))

        next_str = now_str[3] + now_str[:3]
        next_num = int(next_str)
        if dp[next_num] == -1:
            dp[next_num] = 1
            q.append((next_str, command + 'R'))

0개의 댓글