Baekjoon 15661 링크와 스타트 JAVA

https://www.acmicpc.net/problem/15661

15661번: 링크와 스타트

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%2015661

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 사람 수가 주어졌을 때 팀을 두 개로 나누고 이때 만들어지는 능력치의

차가 최소인 값을 구하는 문제다.

 

예전에 풀었던 스타트와 링크의 업그레이드 문제다.

https://soonil.tistory.com/119

Baekjoon 14889 스타트와 링크 JAVA

스타트와 링크는 팀 구성 사람 수를 절반으로 가져가는데 링크와 스타트의 경우

한 팀에 최소 1명 이상만 구성되면 팀이 결성 가능하다는 차이가 있다.

 

해당 문제는 부분집합을 사용해서 해결했으며, 먼저 입력 처리를 받고 부분집합을 만드는데

부분집합은 기저 조건은 index > N로 두었다 1부터 시작했으므로 index == N +1 도 가능

이후 로직은 기저 조건을 허용하지 않으면 먼저 해당 index를 true로 바꾼 뒤 재귀 돌린 것과

false로한 뒤 재귀를 돌리는 방식으로 부분집합을 구성하였고,

기저 조건에 들어오면 먼저 visit에 true인 값과 false값을 카운트하고

만약 두 개의 카운트 값 중 하나라도 2보다 작으면 해당 팀은 구성할 수 없으므로 리턴해주고

(문제에서는 한 명 이상만 팀을 구성하면 된다고 하지만 한명일 경우 능력치가 0이기 때문에 제외시켰다.)

그렇지 않으면 해당 인원만큼 배열을 구성하고 각각의 값들을 배열에 저장한 뒤

 

반복문을 돌면서 팀원의 능력치의 합을 구하고 이후 두 팀의 능력치 차를 최솟값으로 갱신하고

최종적으로 갱신된 값을 출력하는 방식으로 문제를 해결했다.