[백준] 투 포인터 - 1450번: 냅색 문제 (Java)

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

1450번: 냅색문제

문제

세준이는 N개의 물건을 가지고 있고, 최대 C만큼의 무게를 넣을 수 있는 가방을 하나 가지고 있다.

N개의 물건을 가방에 넣는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수이고, C는 10^9보다 작거나 같은 음이아닌 정수이고. 둘째 줄에 물건의 무게가 주어진다. 무게도 10^9보다 작거나 같은 자연수이다.

출력

첫째 줄에 가방에 넣는 방법의 수를 출력한다.

중간에서 만나기 알고리즘 처음 접해서 어려웠던 문제이다.

1. 범위를 반으로 나누어 앞의 절반에서 나올 수 있는 무게의 합의 모든 경우의 수를 리스트 A에 입력한다.
2. 뒤의 절반에서 나올 수 있는 무게의 합의 경우의 수를 리스트 B에 입력한다.
3. 기준 리스트를 정하여 정렬한다.
4. 이분탐색 한다.

풀면서 이 과정을 이해하는데 시간이 정말 오래걸렸다.