[백준] 14889번 스타트와 링크

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

이럴수가.. 힌트가 있었다니..

 

문제가 길면 겁부터 먹고보는 사람이지만 이문제는 골드가 아니니까 뇌에 힘주고 풀었다😤

아니 그리고 나 이거 쓸때 "힌트"라는게 존재하는지 첨알았다 이럴수가;ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

 

 

문제가 먼소린가 싶어서 또 적어봤었지.

한 팀이 된 친구들의 능력치를 모두 더하는 문제이다.

 

그럼 뭘 해야하는가!

 

1. 사람이 몇 명인지 

    → int(input()) 으로 받음. 만약 6명이라고 한다면..

    → people = [0,1,2,3,4,5] 이렇게 사람을 리스트에 넣는다

 

2. 스타트팀 / 링크팀으로 어떻게 나눌 것인지

    → itertools.combinations 사용하여 조합을 구함 = start팀 (0,1,2)

    → start팀에 들어있지 않은 사람 = link팀 (3,4,5) 이런 식으로.

       이건 link = [p for p in people if not in start] 로 했음! people에 있는 사람 중, start에 없는 사람을 link에 넣음

 

3. 각 팀의 능력치 합을 구하기

    → 각 팀에 포함된 사람은 숫자로 표현돼있으므로 그냥 그대로 table[i][j]로 사용하면 됨!

    → i == j 의 경우에는 table에 0이라고 돼있으므로 굳이 if로 처리해주지 않아도 된다! (더해도 0이니까..)

 

 

🙋‍♀️ 작성한 코드

 

# 14889 번 : 스타트와 링크
import itertools
def backtracking_14889():
  n = int(input()) #사람 명 수
  table = [] 
  for _ in range(n):
    table.append(list(map(int, input().split())))

  people = [i for i in range(n)] #사람 목록
  stats = [] #능력치의 차를 저장하는 리스트

  #팀을 나누는 과정
  tmp_team = list(itertools.combinations(range(n), n//2))
  for team in tmp_team:
	
    start = team
    link = [p for p in people if p not in start]

    hap_start = 0 #스타트의 합
    hap_link = 0 #링크의 합
    for i in start:
      for j in start:
        hap_start += table[i][j]

    for i in link:
      for j in link:
        hap_link += table[i][j]
    
    if abs(hap_start - hap_link) == 0: #차가 0이면 더이상 계산 안해도 됨
      print(0) #0 출력하고 끝냄
      return 
    else: 
      stats.append(abs(hap_start - hap_link)) #0이 아니면 리스트에 넣음
    
  print(min(stats)) #최소값을 출력

backtracking_14889()