글 읽기 - 시간초과 질문드립니다..

black01676 1년 전 0

정답 알고리즘과 큰 차이가 없는것같은데 시간초과가 뜹니다 ㅠㅠ

방식은

1) team 나누기 모든경우(def team) 각각 마다

2) 합 구하기 (def team_dfs)

3) 최소값

1,2 번 각각의 dfs를 이용해서 모든 경우를 touch하려고 하였습니다..

도움부탁드려요!

import sys
input = sys.stdin.readline

N = int(input().strip())
Arr = []
for i in range(N) :
    Arr.append(list(map(int, input().split())))

set_ref = set([i for i in range(N)])

def team_dfs (arr, arr_ref, sum) :
    global Arr
    if len(arr) == 2 :
        sum += Arr[arr[0]][arr[1]]
        return sum
    for i in range(len(arr_ref)) :
        if arr_ref[i] not in arr :
            arr.append(arr_ref[i])
            sum = team_dfs(arr, arr_ref, sum)
            arr.pop()
    return sum

def compare (arr1, arr2) :
    sum1, sum2 = 0, 0
    return abs(team_dfs([], arr1, sum1) - team_dfs([], arr2, sum2))  # DFS로 모든 case 합 구해서 빼기

def team (arr, arr3, MinDiff) : #DFS로 2팀으로 나누는 모든 Case
    global N
    if len(arr) == N//2 :
        A = arr
        B = list(set_ref - set(arr))
        temp = compare(A, B)   #2팀으로 나눈 결과 비교
        if MinDiff > temp : #최소값
            MinDiff = temp
        return MinDiff

    for i in range(len(arr3)) :
        if arr3[i] not in arr :
            arr.append(arr3[i])
            MinDiff = team(arr, arr3, MinDiff)
            arr.pop()
    return MinDiff

print (team([], [i for i in range(N)], 100))

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

문제

문제

출처

ICPC

시간초과 질문드립니다..

black01676 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말