스타트와 링크 - (삼성 SW역량 문제) ★★☆

n : 사람 수

t : 입력 받는 능력치 2차원 배열

check : 팀을 구분하기 위해 dfs에서 표시할 배열

def team : 첫번째 선수부터 차례대로 팀을 구성하도록 하는 dfs 함수

(* hap은 def 인자로 넣지 않아도 될 것 같음) - > 따라서 def에는 k와 cnt만 필요

 

 

 

손으로 계산해보면 처음 선수를 넣는 경우와 넣지않는 경우는 결국에는 A team, B team에 각각 속하게 되는 경우인데,

A와 B의 구분이 없으므로 이는 겹치는 경우의 수이다.

 

따라서 마지막 줄 team(1,0,0)에서 k=1로 시작하여 첫번째 선수를 넣는 경우의 수만 따진다.

 

 

 

 if cnt ==n/2 는 내가 포함한 선수가 전체 선수의 반이 되는 시점으로, 팀 가르기가 끝난 경우이다.

따라서 dfs를 하면서 계속 더해준 hap (A team의 총 능력치)와 if문에서 계산한 hap2 (B team의 총 능력치)의 차를 구하여 최솟값을 갱신시킨다.

(* hap도 사실 hap2와 마찬가지로 if안에서 같이 구해줘도 될 듯하다. 괜히 dfs하면서 계산하니 복잡하기만 했다.)

 

hap을 구하는 과정은 다음과 같다.

check 리스트에서 1이 표시된 값을 찾고, 그 표시된 값 다음부터 또 1이 표시된 값을 찾아 능력치를 더해준다.

 

 

 

elif check[i] == 0 은 포함되지 않은 선수를 포함시키는 과정이며, 1로 체크를 해준 뒤 먼저 영입한 선수들과의 능력치를 더해준다. (앞서 말했듯이 이 과정은 마지막에 한번에 하는 것이 좋을 듯 하다.)

선수를 포함시킨 뒤 team(i,hap,cnt+1)을 통해 dfs를 한다.

 

1. def team에서 가장 큰 for문의 범위 range(k,n)를 영입한 선수 뒤에서 선수를 고르도록 k = i를 넣었다.

2. hap은 앞서 말했든 불필요하다고 생각.

3. cnt는 내가 영입한 선수의 명 수를 말한다.

 

주석의 print문은 답이 안나와서 디버깅을 위해서 넣어둔 부분이다.

team(i,hap,cnt+1)에서 i 대신 k+1를 넣어버리는 바람에 cnt와 같은 역할을 하는 결과가 나와서 오류가 났다.

앞으로는 손코딩을 먼저 해보고 신중히 코딩을 하는 습관을 가져야겠다.