[BOJ] 14889 스타트와 링크 자바

문제 : 

전형적인 브루트 포스 문제 중 하나이다. 가능한 모든 경우를 비교해서 최솟값을 출력해야한다. N명의 사람 중 N/2명의 사람을 한 팀에 묶어 S값을 계산한다. 이 때 주의할 점은 N=6일 때, ( 1, 2, 3)이 한 팀인 것은 (2 ,3 ,1)이 한 팀인 것과 같다. 즉 같은 팀인 경우를 또 다시 계산하면 메모리 낭비가 심해진다. 따라서 이러한 경우를 없애야 한다. 

 

팀이 같은 경우를 계산하지 않기 위해 i=start에서부터 반복문을 돌릴 때 다음 dfs인자에 i+1을 넣어준다. 그렇다면 다음 dfs는 최소 i=(예전 start)+1 에서 시작하게 된다. 중복체크는 isVisit[] 배열을 이용한다. 이렇게 n을 줄여나가면서 반복하다가 n==N/2, 즉 반으로 팀이 갈라지게 되면

isVisit배열에서 true인 인덱스와 false인 인덱스를 따로 ArrayList를 생성하여 담는다. 이 인덱스가 다른 팀으로 나누어진 사람의 번호를 의미한다. 그 후 각 ArrayList를 순회하며 S를 계산한다. 그 후 min과 비교하여 최솟값을 저장한다. 

다른 사람들의 풀이와 비교해보니 시간이 매우 차이가 났다. 팀을 나누는 방식에서 차이가 있었다. 조금 더 나은 알고리즘을 고민해봐야겠다.