Partially Committed

https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net 브루트포스로 문제를 해결하기에는 N 이 너무 큰 경우에 시간 초과가 발생할 수 있다. 이때 다양한 방법으로 최적화를 시도할 수 있겠지만, 분할정복처럼 N 을 절반씩 나눠서 연산한 다음에 결과를 합쳐서 문제를 푸는 것을 meet in the middle 알고리즘이라고 한다. 다만, 재귀적으로 반복해서 N/2, N/4 ... 1 처럼 계속 쪼개는 게 아니고 맨 처음에 1회만 반으로 쪼개는 것이다. 예..