[백준] 귀찮음 : 16208번 - Python

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

16208번: 귀찮음

 

 

 

문제의 접근 방법

 

* 현우가 가진 하나의 쇠막대 길이 = a1~an까지의 합.

* 막대는 한 번에 n개로 나눠지는 것이 아니라 두 조각으로 나눈 후, 남은 조각을 또 두 조각으로 나누고... 이 과정을 반복.

* 정렬이 불필요.

 

 

 

내가 막혔던 부분

 

길이 x+y인 막대를 길이 x,y인 두 개의 막대로 자를 때, 두 막대의 길이의 곱인 xy비용이 든다는 부분을 이해하지 못함.

-> 두 동강씩 자르는 과정을 반복적으로 수행하여 n개의 쇠막대를 만든다는 뜻.

 

 

 

문제 풀이 방법

 

(1) 현우가 원하는 쇠막대의 수 n 입력 받기

(2) 쇠막대의 길이들을 n개 입력받기 -> 리스트에 저장

(3) 하나의 쇠 막대의 길이 = 리스트 a의 원소들의 합

(4) sumOfList의 값은 a의 인덱스가 하나씩 계산될 때마다 줄어들고, 비용을 저장하는 변수 result는 a의 i번째 인덱스 값과 sumOfList의 값을 곱한 값이므로 이를 누적해서 더해준다

* 여기서 어떤 순서로 계산을 해도 최종 값은 똑같기 때문에 정렬해줄 필요가 없다!!!

 

 

 

소스코드

n = int(input())

a = list(map(int, input().split()))

result = 0
sumOfList = sum(a)

for i in range(len(a)-1):
    sumOfList -= a[i]
    result += a[i] * sumOfList

print(result)