9019 DSLR _python

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

9019번: DSLR

시 간 초 과

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 접근

쉽게 구현하고 황당하게 틀렸다.

우선 처음엔 긴가민가 했다. 브루트포스같은 느낌인데 새로운 알고리즘의 느낌은 나지가 않고, 그리디 알고리즘을 절대 아니다.

탐색하는 방법을 그려보니 BFS가 최선인듯 했다. 그리고 BFS가 맞더라

 

첫번째 시도

D,S,L,R을 함수로 구현하고 각 상황을 BFS를 사용해 deque에 저장했다.

시간초과

 

두번째 시도

배열을 만들고 중복 계산을 재거했다.

시간초과

 

세번째 시도

배열을 set으로 바꿨다.

결과는 똑같이 시간초과

 

이까지 여러번 제출했더니 한 10번틀렸다.

그러다 문득 든게 다른사람 제출은 어떨까? 봤더니

전부 시간초과였는데 pypy3은 통과였다.

확인해보니 python3로 제출해서 맞춘사람은 단7명. 심지어 코드 공개도 안함

Pypy3로 제출해야만 통과가 된다 이말.

 

네번째 시도

Pypy3로 제출...

통과...

이틀걸렸다 하...

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

코드

from collections import deque
import sys
input = sys.stdin.readline

"""

"""

def D(n):
    return (n*2)%10000
def S(n):
    return 9999 if n==0 else n-1
def L(n):
    return (n%1000)*10 + n//1000
def R(n):
    return (n%10)*1000 + n//10

T = int(input())
for _ in range(T):
    A, B = map(int,input().split())
    queue = deque()
    queue.append((A,""))
    visited = set()
    while queue:
        num, command = queue.popleft()
        if num==B:
            print(command)
            break

        result = D(num)
        if result not in visited:
            visited.add(result)
            queue.append((result, command+"D"))

        result = S(num)
        if result not in visited:
            visited.add(result)
            queue.append((result, command+"S"))

        result = L(num)
        if result not in visited:
            visited.add(result)
            queue.append((result, command+"L"))

        result = R(num)
        if result not in visited:
            visited.add(result)
            queue.append((result, command+"R"))

8308ms