[백준 15661] 링크와 스타트

1. 문제

www.acmicpc.net/problem/15661

15661번: 링크와 스타트

2. 접근 방법

스타트와 링크는 N//2였지만!

링크와 스타트는 팀 당 최소 1명 이상이면 된다 !

 

그래서 여태껏 시간초과를 내다가 드디어 풀었다 !

 

후우~!

 

일단 팀 당 최소 1명 이상이면 되니까

1명, 2명, ..., N//2명 까지만 뽑는 경우의 수를 세면 된다. 

 

N//2이상의 경우 중 N-1명을 뽑는 경우의 수를 예로 들자면,  (N-1명을 뽑는거)랑 (1명을 뽑고 다른 팀에 N-1명을 넣는거)랑 같은 거기 때문에 !

 

이렇게 경우의 수를 뽑아서 각각의 경우에서 나올 수 있는 점수 차이의 최소 값을 구해서 

print할 최종 값을 최소 값으로 계속 갱신해주면 된다.

3. 코드

python

def cal_team(lst):
    sum_team = 0
    for _i in range(len(lst)):
        for _j in range(len(lst)):
            if _i != _j:
                i, j = lst[_i], lst[_j]
                sum_team += board[i][j]
    return sum_team

def comb(s, cnt, n):
    global min_ans, visited
    if cnt == n:
        team1, team2 = [], []
        for i in range(N):
            if visited[i]:
                team1.append(i)
            else:
                team2.append(i)
        if len(team1) * len(team2) == 0:
            return
        sum_team1 = cal_team(team1)
        sum_team2 = cal_team(team2)
        min_ans = min(min_ans, abs(sum_team1 - sum_team2))
        return
    for i in range(s, N):
        visited[i] = True
        comb(i+1, cnt+1, n)
        visited[i] = False

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
min_ans = 1e9
team1, team2 = [], []

visited = [False] * N
for i in range(1, N//2+1):
    comb(0, 0, i)
print(min_ans)

4. 마치며

이제 한 문제 남았다 ! 화이륑