[파이썬] 백준 1450번: 냅색문제

백준 1450번: 냅색문제 1450번: 냅색문제 문제 세준이는 N개의 물건을 가지고 있고, 최대 C만큼의 무게를 넣을 수 있는 가방을 하나 가지고 있다. N개의 물건을 가방에 넣는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 10 9 보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 10 9 보다 작거나 같은 자연수이다. 출력 첫째 줄에 가방에 넣는 방법의 수를 출력한다. 예제 입력 1 복사 2 1 1 1 예제 출력 1 복사 3 예제 입력 2 복사 1 1 1 예제 출력 2... www.acmicpc.net 접근 방법 (핵심 아이디어) N이 최대 30이므로, 모든 부분집합을 구하면 2^30으로 시간초과임. 반절로 나눠서 두개의 부분집합(2^15, 2^15)을 구하고, 이분탐색으로 구해야함. 꽤 유명한 테크닉입니다. 나이브하게 모든 부분집합을 구할수 없으니까, 반절로 나누고 이분...

원문링크 : [파이썬] 백준 1450번: 냅색문제