백준 #14889 스타트와 링크

내 코드

import sys, math
sys.stdin = open("input.txt")
input = sys.stdin.readline

def solve(cnt, idx):
    global min_value, check
    if cnt == m:
        temp = list(all - set(team))
        sum_a = 0
        sum_b = 0
        for i in range(m - 1):
            for j in range(i + 1, m):
                sum_a += arr[team[i]][team[j]]
                sum_a += arr[team[j]][team[i]]
        for i in range(m - 1):
            for j in range(i + 1, m):
                sum_b += arr[temp[i]][temp[j]]
                sum_b += arr[temp[j]][temp[i]]

        value = abs(sum_a - sum_b)
        if min_value > value:
            min_value = value
        check += 1
        if check == end:
            print(min_value)
            exit()

        return

    for i in range(idx + 1, n):
        if not visited[i]:
            visited[i] = True
            team.append(i)
            solve(cnt + 1, i)
            visited[i] = False
            team.pop()

n = int(input())
m = int(n / 2)
arr = [list(map(int, input().split())) for _ in range(n)]
visited = [False] * n
team = []
all = set([i for i in range(n)])
end = math.factorial(n) // (math.factorial(m) ** 2)
min_value = math.inf
check = 0
solve(0, -1)

소름돋았던 코드

import sys
sys.stdin = open("input.txt")
input = sys.stdin.readline

def DFS(L, s, a):
    global res
    if L == N // 2:
        res = min(res, abs(s))
        return
    for i in range(a, N):
        DFS(L + 1, s - row[i] - col[i], i + 1)

N = int(input())
gra = [list(map(int, input().split())) for _ in range(N)]
row = [0] * N
col = [0] * N

tot = 0
for i in range(N):
    for j in range(N):
        row[i] += gra[i][j]
        col[j] += gra[i][j]
        tot += gra[i][j]
        
res = 2147000000
DFS(1, tot - row[0] - col[0], 1)
print(res)
# dddd04032님 풀이

풀이

진짜 자괴감을 많이 느끼면서 풀었던 문제다 ㅜㅜㅜㅜ

시간 초과문제가 해결이 안되어서 스트레스를 정말 많이 받았다.

어떤 팀을 방문 했으면 그 다음 팀부터 dfs를 돌아야하는데 멍청하게 0번 팀부터 다시 돌았다.

itertools를 쓰면 금방 풀렸겠지만 백트래킹을 연습하고 싶어서 사용하지 않았다.(덕분에 슬퍼짐 흑흑)

맞힌사람들 풀이를 보던 도중 소름돋는 풀이를 찾아서 같이 포스팅했다.

행 별로, 열 별로 합들을 구해 저정한 뒤 전체 합에서 팀에 포함시키고 싶은 번호의 팀의 행, 열의 합을 빼서 구하는 방식이다.

시간도 절반정도 줄일 수 있고 코드도 훨씬 간결하다.

정말 대단한 풀이당..!! dddd04032님 감사합니다 ㅠ

p.s

오늘 ICPC Sinchon Winter Algorithm Camp Contest Open 대회에 참가 했는데 4문제나 풀어서 기뻤지만

이문제 때문에 다시 기분이 다운되었다 ㅎㅎㅎ 더 열심히하자!!