[백준 14929] 귀찮아 (SIB) Python3

문제 주소 및 출처 ❕

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

14929번: 귀찮아 (SIB)

 

 

문제 : 14929 귀찮아 (SIB)

 

언어 : Python3

 

 

 

itertools.combinations와 2중 for문을 이용한 경우 시간초과 발생😂

결합법칙을 이용하여 통과😍

 

 

😥 나의 코드 (시간초과)

❌ [itertools 사용] Python3

import itertools

n = int(input())
arr = list(map(int, input().split()))
ans = 0
a = [x for x in range(n)]
v = itertools.combinations(a, 2)
for w in v:
    ans += arr[w[0]] * arr[w[1]]
print(ans)

 

❌ [2중 for문 사용] Python3

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

temp = []
for i in range(1, n):
    temp.append(sum(arr[i:]))

ans = 0
for i in range(n-1):
    ans += arr[i] * temp[i]

print(ans)

 

💬 나의 코드 (성공❤)

📌 Python3

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

# 자신까지의 누적합 배열
temp = [arr[0]]
for i in range(1, n):
    temp.append(temp[i-1]+arr[i])

# a*b+a*c=a*(b+c)를 이용
# 자신의 값 * 자신 이후의 누적합
ans = 0
for i in range(n-1):
    ans += arr[i] * (temp[n-1]-temp[i])  # 전체 누적합 - 자신까지의 누적합

print(ans)