15661

문제풀이

입력

로직

방법 1. 재귀호출

1. 팀의 능력치를 구하는 함수를 작성한다.
2. 팀을 두개로 나누는 재귀 함수를 작성한다.
3. (2)함수를 호출해서 2팀으로 나누는 경우의 수의 집합을 구한다.
4. (3)에서 만든 집합 수만큼 반복한다. a. (1) 함수를 두번 호출 해서 두 팀의 능력치의 차이의 최소값을 구한다.
5. (4)에서 구한 최소값을 반환한다.

방법 2. 비트마스킹 - 팀을 두개로 나누는 것은 부분집합 개념으로 2의 n승까지의 숫자만큼 반복한다. - 이진수를 사용하면 1과 0으로 구분된 두팀으로 나눠진 경우의 수를 모두 표현할 수 있다. - 1을 왼쪽으로 n번 시프트연산하면 2의 지수승이다. - 2의 지수승은 이진수로 n번째 비트가 1이고 나머지가 0이다. - 비트의 위치를 나타낼 때는 오른쪽에서 0번째 부터 시작한다. (0번쨰, 1번째, ... n번째)

1. 팀의 능력치를 구하는 함수를 작성한다.
2. 2의 n승만큼 i를 반복한다. a. j를 n까지 반복한다. b. j번째 팀원이 1이면 스타트팀으로 아니면 링크팀으로 구분한다. - j번째 비트가 1이고 나머지가 0인 숫자와 경우가 i인 숫자의 & 연산결과가 1이다. c. (1)의 함수를 두번 호출해서 i 경우마다 두 팀의 능력치의 차이와 최소값을 구한다.
3. (3)에서 구한 최소값을 반환한다.

맞왜틀

리팩토링

• 14899문제는 신기하게도 항상 n이 짝수이고 항상 n/2명식 나눠지기 때문에 n/2^2만 반복할 수 있는데 이 문제는 매번 팀 구성원이 다르므로 한번에 두 팀의 능력치를 구하려고 하면 시간 초과가 발생한다.
• 두 팀의 길이가 매번 다르기 때문에 매번 n^2 만큼 반복해서 두 팀의 능력치의 차이를 구하는게 아니라 한 팀의 능력치를 각각 구한다음 차이를 구하면 팀 ab만큼만 반복해서 시간을 단축할 수 있다.