리스트 L이 주어졌을 때, 다음 알고리즘을 통해 특수 값 S를 계산할 수 있습니다.
while size of L > 1 is non-zero, do
a := L[0]
b := L[1]
remove L[1]
L[0] := a + b + a*b
return L[0] mod (10^9 + 7)즉, 리스트의 앞에서부터 두 원소를 꺼내 a + b + a×b 연산을 적용하고, 그 결과를 다시 리스트에 넣은 뒤 원소가 하나만 남을 때까지 이 과정을 반복하는 방식입니다. 마지막에 남은 값을 10^9 + 7로 나눈 나머지가 바로 S입니다.
이 문제에서 우리가 구해야 할 것은 리스트 L의 모든 가능한 순열(permutation)에 대해 계산된 S 값들의 평균입니다.
예를 들어 입력이 L = [5, 3, 4]라면 출력은 119가 됩니다. 흥미롭게도 리스트의 모든 순열에 대해 계산되는 S 값이 모두 119로 동일하기 때문에, 그 평균 역시 119가 됩니다.
핵심 아이디어
이 문제의 열쇠는 다음과 같은 수학적 성질에 있습니다.
a + b + a*b = (a + 1) * (b + 1) − 1
연산 결과는 '각 원소에 1을 더한 값들의 곱에서 1을 뺀 것'과 정확히 같습니다. 곱셈은 교환 법칙과 결합 법칙이 성립하므로, 원소를 어떤 순서로 결합하더라도 최종 결과는 항상 다음과 같이 동일합니다.
S = (L[0]+1) * (L[1]+1) * ... * (L[n-1]+1) − 1
따라서 모든 순열에 대해 S 값이 같고, 평균을 구하기 위해 실제로 순열을 생성할 필요 없이 한 번의 곱셈 계산만으로 답을 얻을 수 있습니다. 이렇게 하면 시간 복잡도 O(n)으로 문제를 해결할 수 있습니다.
풀이 단계
- m := 10^9 + 7 (결과가 매우 커질 수 있으므로 나머지 연산용 모듈러 값)
- li := L의 각 원소 x에 대해 x+1을 담은 새로운 리스트
- prod := 1로 초기화
- li의 각 원소 i에 대해 prod에 i를 곱한 뒤 m으로 나머지 연산 수행
- (prod − 1) mod m 을 반환
예제 코드
다음 구현을 통해 더 잘 이해해 보겠습니다.
def solve(L):
m = 10**9+7
li = [x+1 for x in L]
prod = 1
for i in li:
prod *= i
prod %= m
return (prod-1) % m
L = [5,3,4]
print(solve(L))입력
[5,3,4]
출력
119
결과 검증
L = [5, 3, 4]인 경우 각 원소에 1을 더하면 6, 4, 5가 되고, 이들의 곱은 6 × 4 × 5 = 120입니다. 여기서 1을 빼면 119로, 코드의 출력과 일치합니다. 어떤 순열(예: [4, 5, 3], [3, 4, 5] 등)로 계산하더라도 결과는 항상 119이므로, 모든 순열에 대한 S 값의 평균 역시 119가 됩니다.