[BOJ 14889] 스타트와 링크

03 Mar 2026

Reading time ~7 minutes

문제 요약

사람 수 N은 짝수 (4 ≤ N ≤ 20)
N/2명씩 스타트 팀 / 링크 팀으로 나눈다.
같은 팀에 속한 모든 쌍 (i, j)에 대해 시너지 Sij + Sji를 더한 값이 팀 점수
두 팀 점수 차이의 최솟값을 출력

내가 처음 접근한 방식 (메모리 초과가 난 코드)

내 코드는 “가능한 팀 조합을 전부 리스트로 저장”하는 방향이었다.

teams: 가능한 스타트 팀 조합을 전부 저장 (크기: (\binom{N}{N/2}))
counter_teams: 각 팀의 보완 팀(링크 팀)도 전부 저장
팀 내부의 2명 조합도 전부 저장 (combinations_teams, combinations_counter_teams)
그 후 점수를 계산해서 비교

이 방식은 아이디어 자체는 맞지만, 중간 결과를 너무 많이 리스트에 저장해서 메모리가 터졌다.
특히 N=20이면:

팀 조합 개수: (\binom{20}{10} = 184,756)
각 팀마다 2명 조합: (\binom{10}{2} = 45)

즉 “팀 조합을 전부 저장” + “각 팀의 2명 조합까지 저장”을 하면, 파이썬 리스트 오버헤드 때문에 메모리 사용량이 급격히 증가한다.

n = int(input())

matrix = []

for _ in range(n):
    matrix.append(list(map(int, input().split())))

path = []
teams = []
counter_teams = []

def dfs(start):
    if len(path) == (n // 2):
        teams.append(path.copy())
        return
    for x in range(start, n):
        path.append(x)
        dfs(x + 1)
        path.pop()

dfs(0)

for team in teams:
    counter_team = []
    for i in range(n):
        if i not in team:
            counter_team.append(i)
    counter_teams.append(counter_team)

combination_path = []
combination_out = []
combinations_teams = []
combinations_counter_teams = []

def dfs_combination(team, start):
    if len(combination_path) == 2:
        combination_out.append(combination_path.copy())
        return
    for y in range(start, n//2):
        combination_path.append(team[y])
        dfs_combination(team, y + 1)
        combination_path.pop()

for team in teams:
    combination_out = []
    dfs_combination(team, 0)
    combinations_teams.append(combination_out)

for counter_team in counter_teams:
    combination_out = []
    dfs_combination(counter_team, 0)
    combinations_counter_teams.append(combination_out)

scores = []
counter_scores = []

for combinations_team in combinations_teams:
    score = 0
    for combination_team in combinations_team:
        score += matrix[combination_team[0]][combination_team[1]]
        score += matrix[combination_team[1]][combination_team[0]]
    scores.append(score)

for combinations_counter_team in combinations_counter_teams:
    score = 0
    for combination_counter_team in combinations_counter_team:
        score += matrix[combination_counter_team[0]][combination_counter_team[1]]
        score += matrix[combination_counter_team[1]][combination_counter_team[0]]
    counter_scores.append(score)

min_diff = abs(scores[0] - counter_scores[0])

for k in range(len(scores)):
    diff = abs(scores[k] - counter_scores[k])
    if diff < min_diff:
        min_diff = diff

print(min_diff, end='')

GPT가 고쳐준 코드: 무엇이 달라졌나?

아래 개선 코드는 핵심적으로 “저장하지 말고, 탐색하면서 바로 계산”한다.

개선 코드 (요약)

n = int(input())
S = [list(map(int, input().split())) for _ in range(n)]

# i<j 쌍 시너지 미리 합쳐두기: S[i][j] + S[j][i]
W = [[0]*n for _ in range(n)]
for i in range(n):
    for j in range(i+1, n):
        W[i][j] = S[i][j] + S[j][i]

selected = [False] * n
selected[0] = True  # 대칭 제거 (0번은 항상 스타트 팀)

min_diff = 10**9

def dfs(idx, cnt):
    global min_diff

    if cnt == n // 2:
        start_sum = 0
        link_sum = 0
        for i in range(n-1):
            si = selected[i]
            for j in range(i+1, n):
                if si and selected[j]:
                    start_sum += W[i][j]
                elif (not si) and (not selected[j]):
                    link_sum += W[i][j]
        diff = start_sum - link_sum
        if diff < 0:
            diff = -diff
        if diff < min_diff:
            min_diff = diff
        return

    # 남은 사람으로 팀을 다 못 채우면 가지치기
    if cnt + (n - idx) < n // 2:
        return

    for i in range(idx, n):
        if not selected[i]:
            selected[i] = True
            dfs(i + 1, cnt + 1)
            selected[i] = False

dfs(1, 1)
print(min_diff, end='')

개선 포인트 1: 리스트 저장을 거의 없앰 (메모리 절약)

내 코드는 teams, counter_teams, combinations_* 같은 중간 결과를 전부 리스트로 저장했다.

반면 개선 코드는:

selected (True/False)만으로 “현재 스타트 팀 구성”을 표현
팀 조합을 저장하지 않고, DFS가 한 조합을 완성할 때마다 점수를 계산하고 바로 min_diff 갱신

즉, 메모리를 많이 잡아먹는 “거대한 리스트”가 사라진다.

개선 포인트 2: 시너지 `W[i][j] = Sij + Sji`를 미리 계산

팀 점수는 항상 Sij + Sji 형태로 쓰이므로, 매번 더하지 말고:

W[i][j]에 미리 합쳐 둔다 (i<j만 사용)

점수 계산이 훨씬 단순해지고, 반복 계산이 줄어든다.

개선 포인트 3: 대칭 제거 (탐색 절반으로)

“스타트 팀”과 “링크 팀”은 역할만 바꾼 동일한 분할이기 때문에,

0번 사람을 스타트 팀에 고정하면
같은 분할을 두 번 세는 일이 사라진다.

selected[0] = True
dfs(1, 1)

이 한 줄이 탐색 공간을 거의 절반으로 줄여준다.

개선 포인트 4: 가지치기(pruning)

아래 조건은 매우 강력한 가지치기다.

if cnt + (n - idx) < n // 2:
    return

의미:

현재까지 스타트 팀에 cnt명 뽑았고,
앞으로 남은 후보가 (n - idx)명인데,
이걸 다 뽑아도 n//2명을 못 채우면 → 더 볼 필요 없음

불가능한 분기는 빨리 종료한다.

이 문제로 배운 점

1) 조합/백트래킹 문제에서 “모든 경우를 저장”하면 메모리 초과가 나기 쉽다
→ 가능한 한 “탐색하면서 바로 계산”하는 방식으로 바꾸기

2) 대칭 제거는 탐색량을 크게 줄인다
→ 한 명을 특정 팀에 고정하는 트릭은 자주 등장

3) 사전 계산(Precompute)은 반복 계산을 줄이고 코드도 단순해진다
→ W[i][j] = Sij + Sji처럼 “항상 같이 쓰이는 값”은 미리 만들어두기

4) 가지치기(pruning)를 넣으면 체감 성능이 확 좋아진다
→ “남은 후보로 목표를 채울 수 있는가?” 같은 조건은 조합 문제에서 매우 유용