[백준 14889] 스타트와 링크 [C/C++]

문제

14889번: 스타트와 링크

---

풀이

 

N / 2명씩 두 팀을 이룰 때, 각 팀에 속하는 팀원들의 번호로 만들 수 있는 조합에 따른 능력치 합을 구해야 한다.

이때, 두 팀의 능력치 합에 대해 최대한 차이가 없도록 팀원을 정해야 한다.

 

만약 N명이 한 팀이라면, S[0][0] ~ S[N-1][N-1]이 그 팀의 능력치가 된다.

이 팀에서 2/N명을 제외시켜 새로운 팀을 만든다면, 새로운 팀의 팀원 번호와 조합 가능한 모든 S를 제외시키면 두 팀의 능력치의 합을 구할 수 있다. 따라서 각 팀의 번호와 조합 가능한 모든 능력치를 저장해주자.

N명이 모두 한 팀이라면, sum( S[0] ~ S[N-1] )이 그 팀의 능력치( sum_S )가 된다. 두 팀으로 나누었을 때 각 팀의 능력치를 절반이라 생각하고 계산해주자.

 팀원을 한 명씩 모든 경우의 수대로 조합해보며 만약 N / 2명 선택한 경우 팀이 가지는 능력치의 최솟값을 확인하자.

이 과정에서 팀의 능력치가 sum_S / 2보다 작아지면 stat은 음수가 될 것이다. 두 팀의 능력치 합 간의 차이를 계산하는 문제이므로 절댓값으로 변환 후 비교하자.

 N / 2명 선택한 경우가 아니라면, 한 명씩 선택해주고 선택한 인원으로부터 발생하는 능력치를 전부 빼준(stat - S[i])값을 전달해주자.

---

소스코드

보기