글 읽기 - 양 구출 작전 메모리 초과 어떻게 피할 수 있나요?

ibocon 3년 전 1

메모리를 어디서 더 줄일 수 있을까요?

import sys
sys.setrecursionlimit(10 * 5)

def dfs(i):

    s = islands[i][0]
    for c in islands[i][1]:
        s += dfs(c)

    if s < 0:
        return 0
    else:
        return s

N = int(input())
answer = 0

islands = [[0,[]] for _ in range(N + 1)]
for i in range(2, N + 1):
    k = input().split()
    v = int(k[1]) if k[0] == 'S' else -int(k[1])
    islands[i][0] = v
    islands[int(k[2])][1].append(i)

print(dfs(1))

ibocon 3년 전 3

하하.. PyPy3 로 제출하면' 메모리 초과' 고 Python3 로 제출하니 '시간 초과' 뜨는데 해결하는 방법이 로직을 수정하는게 아니라 환경설정을 바꿔야 하네요...

일단 PyPy3 '메모리 초과' 는 피할 수 없고, Python3 '시간 초과'는 input = __import__('sys').stdin.readline 을 추가하면 피할 수 있습니다.

input = __import__('sys').stdin.readline
import sys
sys.setrecursionlimit(10 ** 8)

def dfs(i):
    s = islands[i][0]
    for c in islands[i][1]:
        s += dfs(c)

    if s < 0:
        return 0
    else:
        return s

N = int(input())
answer = 0

islands = [[0,[]] for _ in range(N + 1)]
for i in range(2, N + 1):
    k = input().split()
    v = int(k[1]) if k[0] == 'S' else -int(k[1])
    islands[i][0] = v
    islands[int(k[2])][1].append(i)

print(dfs(1))

flip1945 2년 전 0

정말 감사합니다!

덕분에 바로 풀었네요 ㅎㅎ

jong_p 2년 전 0

감사합니다 도움 받고 갑니다.

danielisdan 1년 전 0

Recursion 관련 문제만 나오면 계속해서 이해할 수 없는 메모리 문제가 있어 계속 밤을 샜었는데 ㅠㅠ 너무 감사드립니다!

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

문제

문제

출처

ICPC

양 구출 작전 메모리 초과 어떻게 피할 수 있나요?

ibocon 3년 전 1

ibocon 3년 전 3

flip1945 2년 전 0

jong_p 2년 전 0

danielisdan 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말