글 읽기 - permutations 을 import해서 사용하니 시간 초과가 나옵니다.

njh7799 5년 전 0

아래와 같이 permutations 를 이용하여 모든 순열을 구하고 2중 for 문을 이용하여 구현하였습니다만, 시간 초과가 나옵니다.

답지 또한 2중 반복문을 사용하여 시간 복잡도의 측면에서 문제가 없을 것이라 예상 하였는데, 어디서 문제가 발생했는지 잘 모르겠습니다.

from itertools import permutations 

def main():
    n=int(input())
    w=[list(map(int, input().split())) for _ in range(n)]
    min=0
    for l in permutations(range(0,n)):
        sum=0
        for i in range(n):
            if w[l[i]][l[(i+1)%n]]==0:
                break
            sum+=w[l[i]][l[(i+1)%n]]
        if min==0 or sum<min:
            min=sum
    print(min)

if __name__ =='__main__':
    main() 

djm03178 5년 전 1

Python3보다 PyPy3가 훨씬 빠릅니다.

그 외에 한 가지 더 고쳐야 할 것은 11번째 줄에 의해 탈출한 경우 min을 갱신하지 않아야 합니다.

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

문제

문제

출처

ICPC

permutations 을 import해서 사용하니 시간 초과가 나옵니다.

njh7799 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말