글 읽기 - 메모리초과 뜹니다. 파이썬 고수분들 도와주세요!

wooljs 6년 전 0

게임판의 크기가 최대 100x100 이라고 할 때,

sys.getsizeof(array.array('H', [i for i in range(100)] ))를 하면 오버헤드 64byte까지 합쳐서 264byte가 되는 것을 확인했습니다.

한 줄 당 264가 100줄 있으니까, 264*100 해도 메모리 한도인 128메가에는 한참 못미치는데,

왜 메모리 초과가 뜨는지 잘 이해가 안됩니다.

하루 종일 이것만 시도하고 있는데 ㅜㅜ 도움 주시면 감사하겠습니다!

from collections import deque
from array import array
N = int(input())
M = []
for _ in range(N):
    M.append(array('H', (int(c) for c in input().split())))

c, q = 0, deque([array('H', [0,0])])
while q:
    y,x = q.popleft()
    if x+y == 2*N-2:
        c+=1
        continue
    w=int(M[y][x])
    if N>y+w:
        q.append(array('H', [y+w,x]))
    if N>x+w:
        q.append(array('H', [y,x+w]))
print(c)

toysmars 6년 전 1

BFS의 너비가 굉장히 넓어질 것 같습니다. 아마 O(2^N) 정도? 큐에 너무 많이 집어 넣을거 같아요.

wooljs 6년 전 0

읽자마자 납득이 되네요. 정말 감사합니다. ㅠㅠ 엄한데서 이유를 찾고있었군요.

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

문제

문제

출처

ICPC

메모리초과 뜹니다. 파이썬 고수분들 도와주세요!

wooljs 6년 전 0

toysmars 6년 전 1

wooljs 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말