글 읽기 - python 백트래킹 시간초과 조언 부탁드립니다.

park3three 3년 전 0

어느 부분이 시간을 가장 많이 잡아먹나요? 두 개 팀에 대한 리스트를 만들어서 계산하는 부분을 고쳐야 하나요?

from itertools import combinations

def BT(depth, N):
    global min_value
    if depth == N:
        start = list(combinations(result[0:N//2], 2))
        link = list(combinations(result[N//2:N], 2))
        start_power = 0
        link_power = 0

        for i in range(len(start)):
            start_power += (team_table[start[i][0]][start[i][1]] + team_table[start[i][1]][start[i][0]])
            link_power += (team_table[link[i][0]][link[i][1]] + team_table[link[i][1]][link[i][0]])

        diff = abs(start_power - link_power)

        if diff < min_value:
            min_value = diff

    for i in range(0, N):
        if visited[i] == 0:
            visited[i] = 1
            result.append(i)
            BT(depth+1, N)
            visited[i] = 0
            result.pop()

N = int(input())
team_table = [list(map(int, input().split())) for _ in range(N)]
visited = [0]*N
result = []
min_value = 0xffffff

BT(0, N)

print(min_value)

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

문제

문제

출처

ICPC

python 백트래킹 시간초과 조언 부탁드립니다.

park3three 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말