groti's blog

1. 문제 해석 https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수이고, C는 10^9보다 작거나 같은 음이아닌 정수이고. 둘째 줄에 물건의 무게가 주어진다. 무게도 10^9보다 작거나 같은 자연수이다. www.acmicpc.net 문제를 읽고 재귀로 완전탐색하면 되겠다 싶었는데 N 제한이 30 인 것을 보고 고민에 빠졌다. 모든 경우를 확인할 때 최대 2^30번을 확인해야 하기 때문이다. 그래서 알아본 Meet in the Middle 알고리즘을 적용하면 수행시간을 크게 줄일 수 있다. (개념 참고: Meet in the Middle) 최대 C만큼의 무게를 담을 수 있는 가방이 있다. N개의 물건이 있..