[Python] 백준/BOJ 14929번: 귀찮아 (SIB) (Silver 4)

💻 Problem

문제 보러 가기

 

n과 xi가 주어진다. n은 10만 이하이고, xi는 절댓값이 100 이하인 정수이다.

 

💡 Approach

문제의 식을 처음 봤을 때는 이중반복문이 생각났다.

하지만 n의 최댓값이 10만(10^5)이므로 이중반복문으로 풀면 시간 초과가 된다.

 

만약 이중반복문으로 푼다고 생각하면

• i가 0일 때, x[0] * x[1] + x[0] * x[2] + ... 이고
  • x[0] * (x[1] + x[2] + ...)
• i가 1일 때, x[1] * x[2] + x[1] * x[3] + ... 이고
  • x[1] * (x[2] + x[3] + ...)
• ...

이런 식일 것이다.

 

이는 각 x[i]가 이후 원소들과 모두 곱해지는 구조이기 때문에 x[i]를 공통 인수로 묶을 수 있다.

x의 모든 원소의 합을 구해놓으면 해당 합에서 x[i]를 빼는 방식으로 계산량을 줄일 수 있다.

이렇게 되면 시간 복잡도는 O(n^2) → O(n)이 된다.

 

✏️ Solution

import sys
input = sys.stdin.readline

n = int(input())
x = list(map(int, input().split()))
total = sum(x)
ans = 0

for i in range(n):
    total -= x[i]
    ans += x[i] * total

print(ans)