240527 [BOJ/백준] 14889. 스타트와 링크

https://www.acmicpc.net/problem/14889

---

나의 코드

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

min_v = 40001
def backtracking(depth, idx):
    global min_v

    if depth == N//2:
        sum_start, sum_link = 0, 0
        for j in range(N):
            for k in range(N):
                if visited[j] and visited[k]:
                    sum_start += ability[j][k]
                if not visited[j] and not visited[k]:
                    sum_link += ability[j][k]
        min_v = min(min_v, abs(sum_start-sum_link))
        return

    for i in range(idx, N):
        if not visited[i]:
            visited[i] = 1
            backtracking(depth+1, i+1)
            visited[i] = 0

backtracking(0, 0)
print(min_v)

결과

---

한 달 전쯤 이 문제를 처음 접했을 때 백트래킹으로 모든 조합을 나누려고 했다. 나눴는데 합을 구할 방법이 도저히 떠오르지 않아서 나눈 상태로 냅뒀다. 그리고 오랜만에 도전하며 그냥 처음부터 다른 사람의 코드를 참고하려 했다. 다른 사람의 코드와 달랐던 부분은 단 한 개. 스타트와 링크 나눌 때 if와 elif로 나누지 않고 if if로 나눠도 되겠다 싶어서 제출했는데 시간초과.. 그 부분이 잘못되었나 싶어서 if와 elif로 나눠서 제출했는데도 시간초과가 났고 readline을 넣어도 시간초과가 났다. 알고보니 난 함수의 끝 부분에 backtracking(depth+1, idx+1)로 썼고 그래서 중복제거를 못해서 시간초과가 난거였다.. 미량이의 도움으로 시간초과 부분 해결하고 처음 생각대로 if, if로 나눠도 된다는 것까지 확인!