백준 14889번 스타트와 링크 (삼성 SW 역량테스트 기출문제)

문제 링크: https://www.acmicpc.net/problem/14889

사용한 알고리즘: Brute Force


 문제에서 N명의 사람을 주고, i,j번째 사람이 한 팀일 경우의 능력치를 입력으로 주고 있습니다. 특이한 점은 i,j 와 j,i의 능력치가 다릅니다. 문제에도 주어지지만 i,j가 한 팀이 된 경우, i,j 와 j,i의 능력치를 모두 팀 능력치에 더해주면 됩니다. 구하고자 하는 값은 두 팀을 만들었을 때 두 팀간의 능력치 차의 최소값입니다.

 기본적으로 N이 최대 20으로 주어졌기 때문에 Brute Force 를 쓰면 해결이 가능합니다.

 문제를 푸는 과정은 다음과 같습니다.

(1) Brute Force를 수행할 함수를 하나 만들어 주었습니다. 이때 이 함수는 1~N 사람을 모두 볼 것입니다. 또한 Stark와 Link라는 두 vector을 들고 갑니다.
i번째 사람을 함수로 돌릴때는 각각 Stark에 넣고 i+1번째 사람으로 넘어가고,
 Stark에 넣었던걸 도로 빼고 i번째 사람을 Link에 넣고 i+1번째 사람으로 넘어갑니다.
이때 Link에 i번째 사람을 넣을시, 앞서 Stark에 넣어놨던 i번째사람을 빼야 됨을 주의해주어야 됩니다.

(2) 함수를 돌리면서 Stark,Link 중 하나의 크기가 N/2가 되었을 경우, 즉 가득 찼을 경우 (두 팀은 모두 N/2명의 사람을 포함해야 합니다.) 남은 사람을 모두 반대 vector에 넣어주고 두 팀의 능력치를 계산후 구하고자 하는 두 팀간의 능력치 차이의 최소값을 최신화 해줍니다.