글 읽기 - 파이썬 거의 비슷한 코드 같은데 메모리초과 나는 코드와 나지 않는 코드

injoon2018 3년 전 1

비슷한 코드 같은데 어떤 것은 메모리 초과가 나고 어떤 것은 통과하는 것 같습니다. break나 return 에서 차이가 나는걸까요?

#메모리 초과 난 코드 
import sys
from itertools import permutations
sys.setrecursionlimit(100000)

N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
order = [i for i in range(0, N)]
permutation_list = list(permutations(order, N))
answer = sys.maxsize

for list in permutation_list:
    temp_sum = 0
    broken = False
    for i in range(len(list)-1):
        if graph[list[i]][list[i+1]] == 0 or graph[list[len(list)-1]][list[0]] ==0:
            broken = True
            break
        else:
            temp_sum += graph[list[i]][list[i+1]]
    if not broken:
        temp_sum += graph[list[len(list)-1]][list[0]]
        answer = min(temp_sum, answer)
print(answer)
################################
#메모리 초과 나지 않은 코드
#출처 https://copy-driven-dev.tistory.com/entry/%EB%B0%B1%EC%A4%80Python10971%EB%B8%8C%EB%A3%A8%ED%8A%B8%ED%8F%AC%EC%8A%A4-%EC%99%B8%ED%8C%90%EC%9B%90-%EC%88%9C%ED%9A%8C-2
import sys
from itertools import permutations
from itertools import permutations

n = int(input())
d= []
for i in range(n):
    d.append([int(a) for a in input().split()])

perm = [i for i in range(n)]
answer = 9123491234
def sum_routes(r):
    global d, n
    tmp = 0
    for i in range(len(r)-1):
        if d[r[i]][r[i+1]] !=0:
            tmp +=d[r[i]][r[i+1]]
        else:
            return -1

    if d[r[-1]][r[0]] ==0:
        return -1
    else:
        tmp += d[r[-1]][r[0]]

    return tmp

for c in permutations(perm):
    tmpans = sum_routes(c)
    if tmpans != -1:
        answer = min(answer, tmpans)

print(answer)

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

문제

문제

출처

ICPC

파이썬 거의 비슷한 코드 같은데 메모리초과 나는 코드와 나지 않는 코드

injoon2018 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말