부분 집합 비트마스크 세기
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
어느 게임에는 기술이 20가지 있고, 플레이어마다 익힌 기술의 집합을 20비트 정수로 나타냅니다. i번 비트가 켜져 있으면 i번 기술을 익힌 것입니다.
플레이어 j가 익힌 기술이 모두 플레이어 i도 익힌 기술이라면, 즉
이면 "j는 i에게 배울 것이 없다"고 합니다. (&는 비트 AND입니다.)
정수 배열 a가 주어질 때, 각 i에 대해 이 조건을 만족하는 j의 개수(j = i 포함)를 구해 배열로 반환하세요.
입출력 예
| a | result |
|---|---|
[1, 3, 2, 0, 7] | [2, 4, 2, 1, 5] |
[5, 5, 4] | [3, 3, 1] |
[6, 9] | [1, 1] |
입출력 예 설명
예 1 — 3(이진수 011)의 부분 집합은 0, 1, 2, 3이고 모두 배열에 있으므로 4입니다. 7(111)은 배열의 모든 값을 포함하므로 5, 0은 자기 자신만 해당하므로 1입니다.
예 2 — 같은 값도 서로의 부분 집합입니다. 5(101)는 5, 5, 4를 모두 포함하지만, 4(100)는 5를 포함하지 않습니다.
예 3 — 6(0110)과 9(1001)는 겹치는 비트가 없어 서로 포함하지 않습니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(a: int[]) → int[]
제한 사항
-
a.length -
a[i]
기대 복잡도
- 시간
- O(N + B * 2^B), B = 20
- 공간
- O(2^B)
입출력 예
| a | 기대 출력 |
|---|---|
[1,3,2,0,7] | [2,4,2,1,5] |
[5,5,4] | [3,3,1] |
[6,9] | [1,1] |
힌트
힌트
모든 쌍을 비교하면 , 값마다 부분 집합을 전부 나열하면 으로 둘 다 너무 느립니다.
값의 범위가 으로 작다는 점을 이용합니다. f[m] = 배열에서 값이 정확히 m인 원소의 개수로 시작해서, f[m]을 "m의 부분 집합인 값의 개수"로 바꾸면 답은 f[a[i]]입니다.
부분 집합 합 DP (SOS DP)
비트를 하나씩 "풀어 주는" 방식으로 누적합을 구합니다.
for b in 0..19:
for m in 0..2^20-1:
if m 의 b번 비트가 켜져 있으면:
f[m] += f[m without bit b]
b번째 바퀴가 끝나면 f[m]은 "m과 위쪽 비트(b보다 큰 비트)는 같고 아래쪽 0..b 비트만 m의 부분 집합인 값들의 개수"가 됩니다. 20바퀴를 다 돌면 모든 부분 집합이 정확히 한 번씩 더해집니다. 같은 부분 집합을 여러 경로로 중복해 세지 않는다는 점이 핵심입니다.
복잡도 목표
입니다. 쌍을 모두 비교하는 풀이는 효율성 테스트에서 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1258 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 11 | 판정만 |
| performance | 60 | 3 | 판정만 |