728x90
반응형
https://www.acmicpc.net/problem/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)
728x90
반응형
'백준 write-up > 정렬 & 그리디' 카테고리의 다른 글
[백준] 너의 핸들은 : 15819번 - Python (0) | 2021.07.30 |
---|---|
[백준] 치킨 TOP N : 11582번 - Python (0) | 2021.07.30 |
[백준] 줄 세우기 : 11536번 - Python (0) | 2021.07.29 |
[백준] 제 2회 IUPC는 잘 개최될 수 있을까? : 12788번 - Python (0) | 2021.07.29 |
[백준] 아우으 우아으이야!! : 15922번 - Python (0) | 2021.07.28 |