Funcia
Lv.4bitmaskdpsos-dp

부분 집합 비트마스크 세기

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

어느 게임에는 기술이 20가지 있고, 플레이어마다 익힌 기술의 집합을 20비트 정수로 나타냅니다. i번 비트가 켜져 있으면 i번 기술을 익힌 것입니다.

플레이어 j가 익힌 기술이 모두 플레이어 i도 익힌 기술이라면, 즉

a[j]&a[i]=a[j]a[j] \mathbin{\&} a[i] = a[j]

이면 "j는 i에게 배울 것이 없다"고 합니다. (&는 비트 AND입니다.)

정수 배열 a가 주어질 때, 각 i에 대해 이 조건을 만족하는 j의 개수(j = i 포함)를 구해 배열로 반환하세요.

입출력 예

aresult
[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[]

제한 사항

  • 1≤N=1 \le N = a.length ≤200,000\le 200{,}000
  • 0≤0 \le a[i] <220=1,048,576< 2^{20} = 1{,}048{,}576

기대 복잡도

시간
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]

힌트

힌트

모든 쌍을 비교하면 O(N2)O(N^2), 값마다 부분 집합을 전부 나열하면 O(320)O(3^{20})으로 둘 다 너무 느립니다.

값의 범위가 2202^{20}으로 작다는 점을 이용합니다. 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바퀴를 다 돌면 모든 부분 집합이 정확히 한 번씩 더해집니다. 같은 부분 집합을 여러 경로로 중복해 세지 않는다는 점이 핵심입니다.

복잡도 목표

O(N+20⋅220)O(N + 20 \cdot 2^{20})입니다. 쌍을 모두 비교하는 풀이는 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251258 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4011판정만
performance603판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.