[python/파이썬] 백준 14247 나무 자르기

[문제 출처]

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

14247번: 나무 자르기

 

[문제 풀이]

 

입력으로는 나무의 그루수이자 나무를 자르러 올라가는 날의 수인 n과 

현재 나무들의 길이, 각 나무들이 하루에 자라는 양이 주어진다.

 

이 모든 입력을 고려하여 가장 많은 양의 나무를 얻는 것이 목적이다.

 

쉽게 생각하면 각 날에 가장 길이가 긴 나무를 자르면 된다고 생각하겠지만 이렇게 하면 많은 양의 나무를 자르지 못한다.

나무가 자라는 속도에 맞춰서 잘라줘야 한다.

 

문제에서는 같은 나무를 여러 번 자를 수 있다고 했지만 최대가 되게 하려면 나무들을 한 번씩만 잘라야 한다.

나무가 자라는 속도가 가장 느린 나무부터 순서대로 잘라줬을 때 가장 많은 양의 나무를 얻을 수 있다.

import sys
input = sys.stdin.readline

n = int(input())

now_h = list(map(int, input().split()))
grow_h = list(map(int, input().split()))

trees = []

for i in range(n):
    trees.append([now_h[i], grow_h[i]])

trees.sort(key = lambda x : x[1])

result = 0
for i in range(n):
    result += trees[i][0] + trees[i][1] * i

print(result)