[BaekJoon] 14889 스타트와 링트

🔦 문제 링크

✍️ 풀이

---

1. 조합을 사용해 스타트 팀의 후보자를 구한다.
2. 나머지 조합은 링크 팀의 후보자이다.
3. 조합에서 2명을 뽑은 조합에서 합을 구한다.
4. 스타트 왈 링크 팀의 총합의 차를 구한다.
5. 해당 과정을 구한 조합만큼 반복한다.

🛠 코드

---

from itertools import combinations

N = int(input())
board = []
for _ in range(N):
    # map을 이용하여 split한 문자열을 int형으로 변환하고 list에 넣는다.
    board.append(list(map(int,input().split())))

num_list = list(range(N)) # 0~N-1 까지의 숫자를 리스트로 만듬

res = float('inf') # min 초기 값 지정할 때 매우 유용

def solve():
    global res # res는 이제 global변수를 사용함

    for cand in combinations(num_list,N//2): # 리스트에서 반절을 뽑음

        start_mem = list(cand) # 반절 그대로 가져감
        link_mem = list(set(num_list) - set(cand)) # 반절 남은 거 가져감

        start_comb = list(combinations(start_mem,2)) # 반절에서 2개를 뽑은 리스트
        link_comb = list(combinations(link_mem, 2))

        start_sum = 0
        for x, y in start_comb: # 반절에서 2개씩 뽑은 리스트 반복
            start_sum += (board[x][y] + board[y][x]) # 총합을 구함

        link_sum = 0
        for x, y in link_comb:
            link_sum += (board[x][y] + board[y][x])

        res = min(res, abs(start_sum - link_sum)) # 최솟값을 구함
    # 조합을 바꿔가며 반복
solve()
print(res)

✍️ 다른 풀이

---

• 내가 풀고 싶었던 방법 (DFS 사용 방법)

1. DFS를 통해 총 인원의 반(N/2)을 선택할 때 까지 함수 진입
2. select가 1이면 스타트 0이면 링크로 구분할 수 있다.
3. 인원의 반을 선택했다면(if cnt == n//2) i, j 모두 1이라면 start팀을 증가시키고 모두 0이라면 link팀을 증가시킴
4. 두 팀의 능력치 차를 최솟값에 기록
5. 이 과정을 모든 DFS가 끝날 때 까지 반복.

🛠 다른 코드

---

import sys

input = sys.stdin.readline

def dfs(idx, cnt):
    global ans
    if cnt == n // 2:
        start, link = 0, 0
        for i in range(n):
            for j in range(n):
                if select[i] and select[j]:
                    start += a[i][j]
                elif not select[i] and not select[j]:
                    link += a[i][j]
        ans = min(ans, abs(start - link))

    for i in range(idx, n):
        if select[i]:
            continue
        select[i] = 1
        dfs(i + 1, cnt + 1)
        select[i] = 0


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

select = [0 for _ in range(n)]
ans = sys.maxsize
dfs(0, 0)
print(ans)

📝 정리

---

• 조합을 쓴다고 무조건 안풀리진 않는다. 적절히 사용하자.
• 순서를 선택할 때 DFS로 구하는 것은 쓸만 한 것 같다.

🎈 참조

---

• hwiyong
• chldkato