SOS dp
sum over subset이라는 이름의 dp입니다. 음이 아닌 정수로 이루어진 길이 $N$의 수열 $A_1$, $A_2$, ... , $A_N$이 주어졌을 때 $0 \le mask < (2^k)$ 인 mask에 대해 $mask | A_i = mask$인 $A_i$의 개수를 구합니다( | 는 bit연산의 or입니다.). 만약 수열 $A$가 0,1,5,6이고 $mask$가 5면 $0|5=5, 1|5=5, 5|5=5, 6|5=7$이므로 답은 3입니다. $mask$가 0일 때 부터 $(2^k) -1$일때 까지의 답을 모두 구하는 문제입니다. $k$는 원하는 값으로 잡으시면 됩니다. $A=(0,1,5,5,6), k=3$이라고 합시다. 숫자끼리 그룹을 지어 줄 것입니다. 먼저, i번째 그룹에는 숫자 i만 들어 있..
2024. 3. 21.
