문제 개요
리스트 A가 주어져 있다고 가정해 보겠습니다. n개의 원소를 가진 리스트는 (2n − 1)개의 공집합이 아닌 부분 리스트를 가질 수 있습니다. 각 부분 리스트에 대해 원소들의 합인 sublist_sum을 계산하고, 이를 S1, S2, S3, ..., S(2N−1)로 표기합니다.
이때 다음과 같은 특별한 합 P를 정의합니다.
P = 2S1 + 2S2 + 2S3 + ... + 2S(2N−1)
목표는 이 P를 구하는 것이며, P가 너무 커질 경우에는 P mod (109 + 7)을 반환하면 됩니다.
예시
입력이 A = [2, 2, 3]이라면, 가능한 부분 리스트와 각각의 기여 값은 다음과 같습니다.
- {2} → 22 = 4
- {2} → 22 = 4
- {3} → 23 = 8
- {2, 2} → 24 = 16
- {2, 3} → 25 = 32
- {2, 3} → 25 = 32
- {2, 2, 3} → 27 = 128
따라서 전체 합은 4 + 4 + 8 + 16 + 32 + 32 + 128 = 224입니다.
접근 방법
모든 부분 리스트를 하나씩 생성하는 방식은 지수 시간이 걸려 비효율적입니다. 대신 곱 전개(생성 함수)의 성질을 활용하면 선형 시간 안에 답을 구할 수 있습니다.
핵심 아이디어는 다음과 같습니다. 각 원소 el에 대해 (1 + 2el)이라는 항을 두고, 이 항들을 모두 곱해 전개하면 각 항은 "해당 원소를 포함하거나 포함하지 않는" 선택에 대응합니다. 즉,
(1 + 2a1) × (1 + 2a2) × ... × (1 + 2an) = Σ 2(부분 집합의 합)
이 값은 정확히 우리가 구하려는 P와 일치합니다. 따라서 알고리즘은 다음 단계로 진행됩니다.
- ans := 1, m := 109 + 7로 초기화합니다.
- A의 각 원소 el에 대해 다음을 수행합니다.
- ans := ans × (1 + (2el mod m))
- ans := ans mod m
- (m + ans − 1) mod m을 반환합니다. 여기서 −1은 공집합에 해당하는 항을 제외하기 위한 보정입니다.
구현 예제
아래 코드를 통해 더 잘 이해해 보겠습니다.
def solve(A):
ans = 1
m = 10**9 + 7
for el in A:
ans *= (1 + pow(2, el, m))
ans %= m
return (m + ans - 1) % m
A = [2, 2, 3]
print(solve(A))
입력
[2, 2, 3]
출력
224
복잡도 분석
이 방법은 배열의 각 원소를 한 번씩만 순회하므로 시간 복잡도는 O(n)입니다. 반면 모든 부분 리스트를 직접 열거하는 완전 탐색 방식은 O(2n)의 시간이 필요하므로, 위 접근법이 훨씬 효율적입니다.