Computer Science/Algorithm
[Baekjoon] Greedy - 16208 귀찮음
ddu0422
2023. 8. 14. 19:40
문제
16208번: 귀찮음
현우는 무슨 이유에선지 길이 a1, ..., an의, 총 n개의 쇠막대가 필요해졌다. 하지만 그가 가진 것은 길이 a1+...+an의 하나의 쇠막대뿐이었다. 현우는 이 막대를 직접 잘라서 원래 필요하던 n개의 쇠
www.acmicpc.net
풀이
"""
n개의 쇠막대
a1 + a2 + a3 + ... + an 하나의 쇠막대
x+y인 막대를 길이 x,y인 두 개의 막대로 자를 때에는 두 막대의 길이의 곱인 xy의 비용이 든다.
최소 비용은?
=== example ===
4
3 5 4 2 => 총 14
5 9 = 45
4 5 = 20
3 2 = 6
"""
n = int(input())
rods = list(map(int, input().split()))[:n]
def solution(rods):
answer = 0
total = sum(rods)
for rod in sorted(rods, reverse=True)[:-1]:
answer += rod * (total - rod)
total -= rod
return answer
print(solution(rods))
채점 결과
배점이 30점인 문제인 것 같다.
