어떤 상자 안에 n개의 원소가 들어 있다. 각각의 원소는 0 이상의 정수이다. 배낭 안에 들어있는 원소의 순서는 중요하지 않다. A에서 0개 이상의 원소를 제거해서 B를 만들 수 있는 경우, "A는 B의 부분 배낭"이라고 한다. 또한 배낭의 무게는 배낭에 들어있는 원소들의 합을 의미한다.

예를 들어 (1, 2, 1, 3, 1)인 배낭과 (3, 1, 1, 1, 2)인 배낭은 같은 상태이다. 하지만 (1, 2, 3, 3)인 배낭은 다르다. (1, 2)와 (3, 1, 1)은 (1, 2, 1, 3, 1)의 부분 배낭이지만, (1, 2, 2)는 부분 배낭이 아니다.

만약 배낭에 들어가 있는 원소가 (1, 2, 1, 3, 1)와 같이 주어졌을 때, 이 배낭의 총 무게의 합은 8이다. 배낭의 정보가 주어졌을 때 무게의 합이 소수(prime-number)인 가능한 부분 배낭의 경우의 수를 구하시오.

#1140 upload 82 done 15 how_to_reg 13

부분 배낭 문제 timer 1s memory 64MB

#1140

부분 배낭 문제 1s 64MB