[백준 14247번] 파이썬 - 나무자르기

백준 14247 - 나무 자르기

시간 제한 2초, 메모리 제한 512MB

# 조건

• 영선이는 나무꾼으로 나무를 구하러 오전에 산에 오른다.
• 산에는 $n$개의 나무가 있는데, 영선이는 하루에 한 나무씩 $n$일 산에 오르며 나무를 잘라갈 것이다.
• 하지만 이 산은 영험한 기운이 있어 나무들이 밤만 되면 매우 빠른 속도로 자라는데, 그 자라는 길이는 나무마다 다르다.
• 따라서, 어느 나무를 먼저 잘라가느냐에 따라서 총 구할 수 있는 나무의 양이 다른데,
• 나무의 처음 길이와 하루에 자라는 양이 주어졌을 때, 영선이가 얻을 수 있는 최대 나무양을 구하시오.
• 참고로, 자른 이후에도 나무는 $0$부터 다시 자라기 때문에 같은 나무를 여러 번 자를 수는 있다.

입력

• 첫째 줄에는 나무의 개수 N개가 있다.
• 나무는 1번부터 N번까지 있다.
• 다음 줄에는 첫날 올라갔을 때 나무의 길이들 Hi가 n개가 순서대로 주어진다.
• 그 다음 줄에는 나무들이 자라는 길이 Ai가 n개가 순서대로 주어진다.

출력

• 영선이가 나무를 잘라서 구할 수 있는 최대 양을 출력하시오.

# 제한

• 1<=n<=100000
• 1<=Hi<=100000
• 1<=Ai<=10000

# 접근 방법

• 그리디적으로 접근할 필요가 있다.
• 얼핏 보기에는 가장 큰 순서대로 자르면 될 것 같지만
• 기다렸다가 한 번에 자르면 되므로 같은 나무를 여러 번 자를 필요가 없다.
• 따라서, 나무의 성장 속도를 기준으로 오름 차순 정렬해주고 각 인덱스 값을 곱한 값을 더해주면 된다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

N = int(input())  
trees = [[0, 0] for _ in range(N)]  
height = list(map(int, input().split()))  
grow = list(map(int, input().split()))  
for i in range(N):  
    trees[i] = [height[i], grow[i]]  

trees.sort(key=lambda x: x[1])  
result = 0  
for idx, val in enumerate(trees):  
    result += val[1] * idx + val[0]  

print(result)