백 트래킹. [14889]

[1. 문제 설명]

2N 명의 사람을 적절히 나눠 N명씩 두개의 팀을 구성하였을 때,

두 팀 간의 능력치 차이가 최소값을 구한다.

 

 

[2. 풀이 접근]

1. 두개의 팀을 구성하는 방법

보통 한개의 집합을 구성하는 경우는 재귀 호출 전,

적당한 자료구조(보통 리스트 같은 계열) 에 값을 저장(푸쉬)하고

다음 재귀로 넘기는 방식으로 구현하지만

 

여기서는 두개의 팀을 구성해야 하므로 이렇게 구현하는 경우 살짝 까다로울 것으로 생각함

 

그래서 한팀(A)은 0명에서 시작하고

다른 한팀(B)은 2N명에서 시작하도록 각각 배열을 준비하여, (두 배열 모두 길이는 2N)

 

각 재귀 호출 전 A 팀은 i번째 사람을 할당하도록 하고. (해당 index 값을 on)

B 팀은 갖고 있던 i번째 사람을 제거하여 (해당 index 값을 off)

 

이 후, 각 팀에 구성된 멤버를 알 수 있도록 하였다.

=> 또한, 특정 멤버를 중복으로 할당 및 제거하지 않도록 유의한다.

=> 코드 참조

 

 

2. 능력치 계산법

문제에 능력치 계산은 멤버 i,j 가 있는 경우 (Si,j + Sj,i) 로 계산해야 함에 주의

 

각 팀을 구성하는 배열은 2N 의 길이를 갖고 있지만,

각 index 에 해당 하는 값이 1 인 것의 개수는 정확히 N 개 임 을 알 수 있다.

 

따라서, 특정 팀 구성 배열을 이중 반복문으로 순회하여,

두 index 에 해당 하는 값이 모두 1 인 경우 

Si,j 값을 팀 능력치에 더 할 수 있으며.

Sj,i 는 이후 반복문 순회 시 다시 참조된다.

 

 

 

[3. 코드]