Jeong in Tech

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

문제 해석

주어진 n 에서 n/2 만큼 스타트팀의 경우의 수를 구한다. 스타트팀을 구하면 남은 인원을 링크팀에 배치한다.

각 팀의 능력치를 구해 합의 차가 가장 작은 경우의 수를 구한다. 

문제 접근

스타트팀 n 에서 n/2 를 순서에 상관없이 뽑는 조합의 문제이다. 

ex) n = 6일 때 [1,2,3] 로 스타트팀을 구성한다면, [1,2,3] 이나 [2,1,3]이나 [3,1,2] 나 순서에 상관 없이 팀의 능력치는 각 팀원들로 만들 수 있는 모든 부분 집합 (x,y) 쌍의 합, 즉, (1,2)+(2,1)+(2,3)+{3,2)+(1,3)+(3,1) 이 될 것이기 때문이다. 

문제 풀이 

시도 끝에 아래 두 가지 풀이 참조 및 비교 

풀이1 : 재귀 이용

출처 - https://gobae.tistory.com/50

풀이2 : 구현 이용

출처 - https://github.com/jlee0505/algorithm-study/pull/1/commits/df6a36b419ef225e0d9196fc7126a3e762a0d194

배운 것 

1. min 값을 각각 0, MIN_SAFE_INTEGER, MAX_SAFE_INTEGER 의 차이:

MIN_SAFE_INTEGER, MAX_SAFE_INTEGER 는 각각 -9007199254740991, +9007199254740991 을 의미한다.

아래 코드의 min 의 초기 할당을 각각 0, MIN_SAFE_INTEGER, MAX_SAFE_INTEGER 으로 했을 때의 차이를 생각해보자.

min = Math.min(min, Math.abs(sSum - lSum));

2.  재귀로 풀 때와 구현으로 풀 때의 장단점:

첫 번째 제출은 풀이1(재귀)의 결과, 두 번째 제출은 풀이 2(구현)의 결과이다. 구현으로 풀면 가독성이 올라가고 직관적 이해가 쉽다는 장점이 있지만, 재귀로 푸는 것이 시간,공간 복잡도가 압도적으로 높다.

재귀는 여전히 어렵다.