Meet in the middle. [1450]

[1. 문제 설명]

N 개의 물건을 최대 C 만큼의 무게를 넣을 수 있는 가방에 넣을 수 있는 경우의 수를 구한다.

 

N 은 30 이하의 자연수

C 는 10억 이하의 자연수

---

[2. 풀이 접근]

이 문제는 동적 계획법으로 풀이가 가능하다.

단, 완전 탐색 중

i 번째 물건을 포함할지 말지를 결정할 때, 아래에 대해서 메모이제이션 할 수 있어야 한다.

• i번째 물건의 index
• 현재까지 누적된 무게

그러나 문제에서 C 는 최대 10억이 될 수 있으므로, 메모리가 부족하여,

다른 접근법이 필요하다.

 

다시 완전 탐색으로 돌아와서 생각해보면,

문제는 탐색의 개수가 너무 많다는 것이다.

 

재귀의 각 단계에서 i번째 물건 선택여부가 존재하니,

총 탐색 개수는 2^N  이다.

N 이 최대 30이니, 대략 10억 정도 된다.

 

여기서 Meet in the middle 알고리즘을 생각해볼 수 있다.

 

Meet in the middle 알고리즘은 하나의 그룹을 완전탐색으로 시간 내 해결하지 못할 때,

하나의 그룹을 두 그룹으로 나누고 각 그룹에 대해서 탐색 한 뒤,

나중에 결과를 다시 조합해보는 방식이다.

 

N 이 최대 30 이니, 절반하면 15 가 되고, 이 그룹에 대해서 탐색개수는 2¹⁵= 32768 이므로

각 그룹에 대해서는 먼저 시간내에 해결 할 수 있다.

 

다음은 그룹을 조합하는 방식이다.

[0, 15) 그룹을 A

[15, 30) 그룹을 B 라 했을 때

 

B 그룹을 대상으로 한 탐색에서 선별된 집합 내 원소의 합이 배열에 저장되어 있다.

이 배열을 먼저 오름차순으로 정렬한다. 

 

그래고 이 배열에서

C - A[j] 의 upper_bound 가 존재하는 index 를 찾는 것이다.

 

배열이 정렬되어 있으니 위 탐색 시간은 O(logn) 이 된다.

 

이 index 가 문제에 조건에 맞는

A 그룹에서  j 번째 집합과 B 그룹에서 집합을 재조합한 개수가 된다.

 

C - A[j] 가 음수인 경우는 index 가 0일 것이고,

C - A[j] 가 0 인 경우는 index 가 1이 된다.

이 부분은 명확하다.

 

여기서 헷갈릴만한 부분은 C - A[j] > 0 인 것이다.

예를 들어, A 의 한 집합이 5 이고 C 가 20 이라 해보자.

 

15 이하를 만족하는 B 그룹내 집합이 아래와 같을 때,

[1, 2, 3, 4 ... )    이고 구한 index 가 10

 

합계 1, 2, 3 ,4 를 조합한 개수가 +a 가 되는 것이 맞다고 생각 할 수 있다.

물론 이는 당연한 것이다.

 

그렇다고, 위의 것을 다시 재조합 할 필요가 없다.

이러한 조합들은 index: 10 이전에 어딘가에 존재하기 때문이다.

 

완전 탐색은 이러한 경우를 놓치지 않는다.

---

[3. 코드]