문제 소개
중복된 값이 포함될 수도 있는 n개의 요소를 가진 배열 A가 주어졌다고 가정해 보겠습니다. 임의의 부분 집합 s에 대해 max(s)는 해당 집합의 최댓값, min(s)은 최솟값을 의미합니다. 우리가 구해야 할 것은 배열의 모든 부분 집합에 대해 max(s) − min(s)를 계산한 값들의 총합입니다.
예를 들어 입력이 A = [1, 3, 4]라면 출력은 9가 됩니다.
예시 검증
[1, 3, 4]의 모든 부분 집합과 각각의 max(s) − min(s) 값은 다음과 같습니다.
- {1}, {3}, {4} : 각각 0
- {1, 3} : 3 − 1 = 2
- {1, 4} : 4 − 1 = 3
- {3, 4} : 4 − 3 = 1
- {1, 3, 4} : 4 − 1 = 3
모두 더하면 0 + 0 + 0 + 2 + 3 + 1 + 3 = 9가 됩니다.
접근 방식
모든 부분 집합을 직접 생성하면 시간 복잡도가 O(2ⁿ)로 매우 비효율적입니다. 대신 각 원소가 '최댓값' 또는 '최솟값'으로 등장하는 횟수를 세면 문제를 선형 시간에 해결할 수 있습니다.
배열을 오름차순으로 정렬하면, 정렬된 위치 j의 원소 A[j]는 다음 규칙을 따릅니다.
- A[j] 자신과 그 앞쪽(작거나 같은) 원소들을 조합한 부분 집합에서는 A[j]가 최댓값이 되며, 이러한 경우의 수는 2ʲ개입니다.
- A[j] 자신과 그 뒤쪽(크거나 같은) 원소들을 조합한 부분 집합에서는 A[j]가 최솟값이 되며, 이러한 경우의 수는 2ⁿ⁻¹⁻ʲ개입니다.
따라서 정답은 Σ A[j] × 2ʲ − Σ A[j] × 2ⁿ⁻¹⁻ʲ이며, 이를 호너(Horner) 방식처럼 반복문 한 번으로 계산할 수 있습니다. 큰 수 오버플로를 방지하기 위해 매 단계마다 모듈로 연산(N = 10⁹ + 7)을 적용합니다.
알고리즘 단계
- n := 배열 A의 크기
- 배열 A를 오름차순으로 정렬
- sum_min := 0, sum_max := 0으로 초기화
- i를 0부터 n−1까지 반복:
- sum_max := 2 × sum_max + A[n−1−i]
- sum_max := sum_max mod N
- sum_min := 2 × sum_min + A[i]
- sum_min := sum_min mod N
- (sum_max − sum_min + N) mod N 반환
구현 예제
다음 구현을 통해 동작 방식을 더 잘 이해할 수 있습니다.
N = 1000000007
def get_max_min_diff(A):
n = len(A)
A.sort()
sum_min = 0
sum_max = 0
for i in range(0, n):
sum_max = 2 * sum_max + A[n-1-i]
sum_max %= N
sum_min = 2 * sum_min + A[i]
sum_min %= N
return (sum_max - sum_min + N) % N
A = [1, 3, 4]
print(get_max_min_diff(A))
입력
[1, 3, 4]
출력
9
복잡도 분석
정렬에 O(n log n), 배열 순회에 O(n)이 소요되므로 전체 시간 복잡도는 O(n log n)이며, 추가 공간 복잡도는 O(1)입니다. 모든 부분 집합을 탐색하는 완전 탐색(O(2ⁿ)) 방식에 비해 훨씬 효율적인 해법입니다.