글 읽기 - 파이썬 메모리초과 질문드립니다.

pepper_mis 3년 전 0

85퍼센트쯤에서 메모리 초과가 납니다.

dp에다가 문자랑 이전값을 저장해두게 만들었는데, 이런식으로 하면 안되는건가요?

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

T = int(input())
for _ in range(T):
    A, B = map(int, input().split())
    dp = [['0', -1] for i in range(10000)]
    dp[A] = ['0', -2]

    queue = deque()
    queue.append(A)

    while queue:
        n = queue.popleft()
        if n == B:
            break

        #D : n을 두배로
        if dp[n*2%10000][1] == -1: 
            queue.append(n*2%10000)
            dp[n*2%10000][0] = 'D'
            dp[n*2%10000][1] = n

        #S : n-1
        if n-1 == -1:
            queue.append(9999)
            dp[9999] = ['S', n]
        elif dp[n-1][1] == -1:
            queue.append(n-1)
            dp[n-1][0] = 'S'
            dp[n-1][1] = n

        if n!=0:
            #L : 각 자릿수를 왼편으로
            L_index = int(n % 1000 * 10 + n / 1000)
            if dp[L_index][1] == -1: 
                queue.append(L_index)
                dp[L_index][0] = 'L'
                dp[L_index][1] = n

            #R : 각 자릿수를 오른편으로
            R_index = int(n % 10 * 1000 + n // 10)
            if dp[R_index][1] == -1: 
                queue.append(R_index)
                dp[R_index][0] = 'R'
                dp[R_index][1] = n

    i = B
    result = [dp[i][0]]
    while dp[i][1] != -2:
        i = dp[i][1]
        result.append(dp[i][0])
        if dp[i][0] == '0':
            break
    for i in range(len(result)-2, -1, -1):
        print(result[i], end='')
    print()

crypt9 3년 전 1

9999 는 queue 에 무한정 들어갈 수 있네요.

line 27 에 아래 조건 추가하니 pypy3 는 AC 받네요

if dp[9999][1]==-1:

pepper_mis 3년 전 0

9999에 방문 확인이 안됐었네요!! 감사합니다!!!

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

문제

문제

출처

ICPC

파이썬 메모리초과 질문드립니다.

pepper_mis 3년 전 0

crypt9 3년 전 1

pepper_mis 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말