Posted 2018-08-31Updated 2021-07-17Algorithm

스타트와링크

삼성 코딩 테스트 기출 문제이다.

시뮬레이션 + 조합 으로 해결하였다.

풀이

플로우는 다음과 같다.

우선, 팀을 배분하는 방법부터 보자.

총 6명이 있다고 하자 : 1번, 2번, 3번, 4번, 5번, 6번

6명이므로 3명 / 3명으로 팀을 나누어야한다.

1번은 5명 중 2명과 팀을 이룬다. 즉, ₅C₂

(1, 2, 3)
(1, 2, 4)
(1, 2, 5)
(1, 2, 6)
(1, 3, 4)
(1, 3, 5)
(1, 3, 6)
(1, 4, 5)
(1, 4, 6)
(1, 5, 6)

위와 같이 1번이 팀을 이루면, 나머지 사람들이 자동적으로 팀을 이루게 된다.

이제, 배분한 팀 각각의 능력치의 합을 구한다.

(1, 2, 3) 을 예로 들자. 1번이 2번, 3번과 팀을 이루었으니 (4, 5, 6)이 한 팀을 이룬다.

다음 배열을 이용해 계산한다.

마지막으로, 두 팀 간의 능력치 차이를 구한다.

위에서 배분한 팀 각각의 능력치의 합을 구하였으므로, 쉽게 차를 구할 수 있다.