스타트와 링크
4번째 시도.
접근 방법(생각한 부분) 자료 구조 입력 데이터 N, int[ ][ ] map 첫번째 팀 팀원 번호 저장 : int[ ] teamA =>하나만 저장하면 될 거라고 생각해서 하나만 만들었었다.
알고리즘 재귀함수 void go(i,index) : i = i번째 사람, index : 한 팀내에서 인덱스. N/2가 최대. 1. 정답 찾은 경우 : if(index == (N/2) +1) 2. 불가능한 경우 : if(index > (N/2) + 1) 3. 다음 경우 호출 1) i번째를 선택하는 경우 : go(i+1, index+1) 2) i번째를 선택하지 않는 경우 : go(i+1,index) 4. 능력치 합 계산 : 구현❌ if(i==j) continue; 🔵
생각하지 못한 부분 3. 다음 경우 호출 1) i번째를 선택하는 경우 go(i+1, index+1) 에서 재귀함수가 리턴되고 난 후에는 i를 팀에서 다시 빼줘야한다!⭐️⭐️⭐️⭐️⭐️ 그래야 i가 아닌 다른 사람이 들어가는 경우의 수를 처리할 수 있기 때문이다!!!
솔루션
자료구조 각 팀원 번호 저장하는 팀 자료구조는 ArrayList f,s =>팀원을 첫번째 팀에 넣는 경우 두번째 팀에 넣는 경우에 따라서 팀원을 넣었다가 뺐다가를 반복해야한다.
능력치합 차이 계산 Sf += a[f.get(i)][f.get(j)]; Ss += a[s.get(i)][s.get(j)] 능력치 차이 = |Sf - Ss|
재귀함수 : 능력치합의 차이 리턴 정답이 되는 변수 ans = -1로 초기화. 첫번째 팀을 선택하는 경우 : 재귀함수 호출을 통해 능력치합의 차이를 t1이라고 할 때, t1의 최솟값을 ans에 저장한다. if(ans == -1) {ans = t1}, if(t1<ans){ans = t1;} =>if(ans == -1 || t1 != -1 && t1<ans) {ans = t1;}//t1에서 최솟값 ans 두번째 팀을 선택하는 경우 ans도 마찬가지로 t2의 최솟값 ans t1최솟값 ans에 저장, 이 ans와 t2최솟값 ans를 비교해서 ans의 최솟값을 정답으로 리턴한다!⭐️❤️
불가능한 경우 먼저 제시(백트랙킹)⭐️⭐️⭐️⭐️⭐️ f.size() > N/2 또는 s.size() > N/2 이면 바로 리턴(-1)!
정답 찾은 경우⭐️⭐️⭐️⭐️⭐️ index == N인경우, 추가 조건 검사해줘야한다!!!!!! index==N임에도 불구하고 f.size() < N/2 또는 s.size() < N/2인 경우 리턴( -1)!!! 그렇지 않으면 능력치합의 차이를 리턴한다!
Last updated