[코딩인터뷰] 백준 16437번

16437번

16437번 양 구출 작전 문제는 "파이썬으로 풀지 말라는게 아닐까" 라는 느낌의 채점 기준이었습니다. 로직이 틀리지 않은거 같은데 왜 통과를 못하고 '메모리 초과' 가 뜰까 싶어서 C++ 정답 코드를 둘러봤는데 로직이 동일한 정답이 있었습니다. 그래서 '어? 환경설정 문젠가?' 싶어서 일단 C++ 정답으로 문제 정답 처리하고 파이썬으로 통과된 코드를 보고 환경설정을 좀 했더니 통과가 되었습니다. 정리하자면,

• 'PyPy 3' 로 제출하면 '메모리 초과' 가 발생합니다.
• 'Python 3' 로 제출하면 '시간 초과' 가 발생합니다.

PyPy3 메모리 초과는 아무래도 BFS 방식으로 풀어야 해결할 수 있어 보이고, Python 3 시간초과는 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))