[BaekJoon] 14889 스타트와 링트

pyh8618·2020년 9월 26일
0
post-thumbnail

🔦 문제 링크

✍️ 풀이


  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로 구하는 것은 쓸만 한 것 같다.

🎈 참조


profile
Go Go

0개의 댓글