글 읽기 - DSLR 테스트 케이스들 찾아보는데 왜 틀린건지 모르겠습니다.....

(追記) (追記ここまで)

DSLR 테스트 케이스들 찾아보는데 왜 틀린건지 모르겠습니다.....

9019번 - DSLR

06vfsunny 5달 전 0

먼저 입력이

1
9073 151

이렇게 주어졌을 때 제 코드가 출력을

DDRSDDSLL

이렇게 하는데 틀렸다고 나오네요....

제가 계산을 잘못한 것인지 모르겠으나 일단 제 출력이 틀린 것 같지는 않은데 말입니다.

그냥 테스트 케이스에서 전체적으로 다 틀렸다고 나오는 것 같은데 제 코드 출력들을 보면 틀린 것 같지는 않습니다...

혹시 뭐 때문에 틀리는건지 알려주실 수 있으실까요??

from collections import deque
result_list=[]
def S(n):
 if n-1==0:
 return 9999
 return n-1
def D(n):
 return (n*2)%10000
def L(n):
 numlist=list(str(n))
 numlist.append(numlist.pop(0))
 return int(''.join(numlist))
def R(n):
 numlist=list(str(n))
 numlist.insert(0, numlist.pop())
 return int(''.join(numlist))
test=int(input())
for t in range(test):
 start, end=map(int, input().split())
 dslrque=deque()
 dslrque.append((start, ''))
 visited=set()
 while dslrque:
 now=dslrque.popleft()
 s=S(now[0])
 d=D(now[0])
 if s==end:
 #print(s)
 result=now[1]+'S'
 break
 if d==end:
 #print(d)
 result=now[1]+'D'
 break
 if not s in visited:
 dslrque.append((s, now[1]+'S'))
 visited.add(s)
 if not d in visited:
 dslrque.append((d, now[1]+'D'))
 visited.add(d)
 if now[0]//10>0:
 l=L(now[0])
 r=R(now[0])
 if l==end:
 #print(l)
 result=now[1]+'L'
 break
 if R==end:
 #print(r)
 result=now[1]+'R'
 break
 if not l in visited:
 dslrque.append((l, now[1]+'L'))
 visited.add(l)
 if not r in visited:
 dslrque.append((r, now[1]+'R'))
 visited.add(r)
 result_list.append(result)
for re in result_list:
 print(re)

jun83 5달 전 0

D빼고 모든 연산이 구현이 잘못되었습니다. 탐색 부분이 잘못되었습니다. 시작 지점을 다시 탐색할 수 있습니다.

추가로 현재 S,L,R 구현 방식으로는 올바르게 고쳐도 시간초과가 발생합니다. 리스트를 생성하고 다시 합쳐서 문자열로 만들고 정수로 바꾸는 것은 매우 느립니다. 다른 방식을 고안해보시면 좋을 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC