1450_냅색문제

https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net Meet in Middle알고리즘을 이용해보라고 힌트가 주어져 있는 문제이다. 위 문제같은 경우, 쉽게 생각하면 주어진 배열중에서 합이 c가 넘지않는 부분배열의 개수를 구하는 문제라고 생각해ㅗㄷ 좋을 것이다. 예를들어 [ 1, 2, ,3 , 4, 5,6 ] 해당 6개의 짐이 있다면 합이 10을 넘지않는 부분집합의 개수를 구하는 문제로 봐도 될 것이다. 이런 경우 모든 배열을 한번씩 탐색하면 굉장히..