8047 : 부분집합의 합
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 양의 정수가 주어집니다. 이 수들의 부분집합 중 원소들의 합이 정확히 $X$가 되도록 만들 수 있는지 판별하는 프로그램을 작성하시오.
(가장 단순한 동적 계획법은 $O(N \times X)$이지만, 비트셋(Bitset) 최적화를 적용하면 상수 시간에 가깝게 속도를 단축할 수 있는 대표적인 비트 평행 문제 중 하나입니다.)
[제약 조건]
• $1 \le N \le 100$
• $1 \le X \le 100{,}000$
• $1 \le w_i \le 100{,}000$
(가장 단순한 동적 계획법은 $O(N \times X)$이지만, 비트셋(Bitset) 최적화를 적용하면 상수 시간에 가깝게 속도를 단축할 수 있는 대표적인 비트 평행 문제 중 하나입니다.)
[제약 조건]
• $1 \le N \le 100$
• $1 \le X \le 100{,}000$
• $1 \le w_i \le 100{,}000$
입력 설명
첫째 줄에 원소의 개수 $N$과 목표 합 $X$가 공백으로 구분되어 주어집니다. ($1 \le N \le 100$, $1 \le X \le 100,000$)
둘째 줄에 $N$개의 정수 $w_1, w_2, \ldots, w_N$이 공백으로 구분되어 주어집니다. ($1 \le w_i \le 100,000$)
둘째 줄에 $N$개의 정수 $w_1, w_2, \ldots, w_N$이 공백으로 구분되어 주어집니다. ($1 \le w_i \le 100,000$)
출력 설명
목표 합 부분집합의 합으로 만들 수 있다면
YES를, 불가능하다면 NO를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 10
2 3 5 8
출력 예시
COPY
복사되었습니다!
복사되었습니다!
YES도움
이 문제는 부분집합 합(Subset Sum) 문제로 배낭 문제의 일종입니다.
파이썬에서는 정수의 비트 크기에 제한이 없고 비트 연산이 하드웨어 수준에서 병렬 처리(Bit-parallel)되므로,
파이썬에서는 정수의 비트 크기에 제한이 없고 비트 연산이 하드웨어 수준에서 병렬 처리(Bit-parallel)되므로,
dp 배열을 거대한 하나의 정수로 정의하여 dp |= (dp << w) 와 같은 단 한 줄의 비트 연산으로 갱신하는 비트셋 기법을 적용할 수 있습니다. 이를 통해 원래 $O(N \times X)$ 걸리는 연산 속도를 64분의 1 이상 단축할 수 있습니다.