[BOJ] Python 백준 23827번 수열 (Easy) 실버 4

https://www.acmicpc.net/problem/23827

23827번: 수열 (Easy)

 

문제 풀이

---

문제를 좀 더 쉽게 설명하자면 길이가 N개인 수열이 있는데 여기서 두 개를 뽑아 서로 곱한 값을 모든 경우의 수에서 다 더한 뒤 1000000007로 나눈 값을 출력하라는 뜻이다.

 

즉, 수학의 조합(Combination)을 떠올리면 된다.

 

하지만 제한 조건을 잘 봐야한다.

 

수열의 길이는 최대 500000(50만)이 될 수 있으며 평소 조합을 구하는 방식대로 첫 번째 원소부터 완전 탐색, 두 번째 원소부터 완전 탐색 ... 이렇게 반복하면 O(n^2)의 시간 복잡도가 걸리므로 시간 초과가 날 수밖에 없다.

 

따라서 어떻게 해야되나 고민을 해본 결과 예제에서 힌트를 얻을 수 있었다.

 

예제는 '1 x 2 + 2 x 3 + 1 x 3 = 11' 이렇게 있었다.

 

이걸 원래 조합 구하는 방식으로 순서를 조금 바꿔보면 '1 x 2 + 1 x 3 + 2 x 3 = 11' 이렇게 나타낼 수 있고 조금만 더 이해하기 쉽게 바꾸면 '1 x (2 + 3) + 2 x 3 = 11' 이렇게 나타낼 수 있다.

 

즉 문제가 원하는 답은 각 원소와 해당 원소의 뒷 원소들의 합을 곱하고 이를 다 더한 값에 1000000007로 나눈 결과를 원하는 것이었다.

 

이렇게 하면 처음 수열의 합을 구할때 O(n), 수열 탐색할 때 O(n), 총 O(n)의 시간 복잡도가 걸리므로 시간 초과가 나지 않을 것이다.

 

다음은 전체 코드다.

 

n=int(input())
num_list=list(map(int,input().split()))
sum_list=sum(num_list)
res=0
for i in num_list:
    sum_list-=i
    res=(res+i*sum_list)%1000000007
print(res)

 

원리만 떠올린다면 구현 자체는 아주 쉬운 문제였다.

 

3번째 줄에서 sum() 함수는 O(n)의 시간 복잡도가 걸린다.

 

5번째 줄의 반복문에서는 해당 원소를 리스트의 합에서 빼주고 해당 원소와 리스트의 합을 곱한 값을 결과값(res)에 더하면서 1000000007의 나머지로 갱신하면 끝이다.

 

결과 화면

 

테스트 케이스를 이용하여 원리를 떠올리는 것이 중요한 문제인 것 같다.