글 읽기 - 파이썬 시간초과 질문

vywogns123 3년 전 0

자꾸만 시간초과가뜨는데 어디서 줄여야할까요.. ㅠㅠ 하루종일봐도 못찾겠습니다

from itertools import combinations
n = int(input())
arr = []
v = []
ans = 1e9
c_range = [x for x in range(n)]
for _ in range(n):
    arr.append(list(map(int,input().split())))

for team_a in combinations(c_range, n//2):
    if team_a in v:
        continue
    team_b = tuple(x for x in c_range if x not in team_a)
    v.append(team_b)
    sum_a = 0
    sum_b = 0
    for a, b in combinations([x for x in range(n//2)],2):
        sum_a += arr[team_a[a]][team_a[b]]+arr[team_a[b]][team_a[a]]
        sum_b += arr[team_b[a]][team_b[b]]+arr[team_b[b]][team_b[a]]
    ans = min(ans,abs(sum_a - sum_b))

print(ans)

gkgg123 3년 전 1

팀을 구하는것과 팀 점수를 더하는 부분에서 시간이 오래걸린것 같습니다.

그 부분만 고치니 쉽게 통과되네요

from itertools import combinations
n = int(input())
arr = []
v = []
ans = 1e9
# 전체팀을 집합으로 구해놓는게 시간상 더 쉽게 구할수 있습니다.
total_team = set(range(0,n))
c_range = [x for x in range(n)]
for _ in range(n):
    arr.append(list(map(int,input().split())))

for team_a in combinations(c_range, n//2):
    # 그리고 team_b는 tuple로 하는 것보다 집합의 차집합을 통해 쉽게 구할수 있습니다.
    team_b = list(total_team - set(team_a))
    sum_a = 0
    sum_b = 0
    # 여기서 시간을 많이 나간것 같습니다.
    # combination 대신 직접 range를 돌리면서 하는게 더 빠를 것 같습니다.
    for index_a in range(n//2):
        for index_b in range(index_a+1,n//2):
            sum_a += arr[team_a[index_a]][team_a[index_b]]+arr[team_a[index_b]][team_a[index_a]]
            sum_b += arr[team_b[index_a]][team_b[index_b]]+arr[team_b[index_b]][team_b[index_a]]
    temp = abs(sum_a-sum_b)
    
    if temp<ans:
        ans = temp
print(ans)

vywogns123 3년 전 0

combination 대신 직접 range로 돌려도 안됐었는데 집합을 사용하지 않아 팀 구하는 부분에서 시간초과가 뜬것 같네요 ㅠㅠㅠ 정말 감사합니다. 많이 배워 갑니다!

sb00lgs 2년 전 0

team_b 구하는 법을 차집합을 이용해서 구하는 법을 답변으로 알려주셨는데,

추가로 combinations로 구한 값을 보면 앞에서 중간으로, 뒤에서 중간으로의 값이 각각 team_a와 team_b에 해당함을 볼 수 있습니다.

c = combinations(c_range, n // 2)
for i in range(n // 2):
    team_a = c[i]
    team_b = c[-1-i]

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

문제

문제

출처

ICPC

파이썬 시간초과 질문

vywogns123 3년 전 0

gkgg123 3년 전 1

vywogns123 3년 전 0

sb00lgs 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말