[Python] 백준 14247 나무 자르기

 

문제 분석

• n개의 나무
• 하루에 한 나무씩 / n일 산에 오르며 나무를 잘라갈 것이다.
• 밤이 되면 나무는 빠른 속도로 자라는데 자라는 길이는 나무마다 다름
• 어느 나무를 잘라가느냐에 따라 총 구할 수 있는 나무의 양이 다름
  
  
• 나무의 처음 길이와 하루에 자라는 양이 주어졌을 때, 영선이가 얻을 수 있는 최대 나무 양을 구하라
• 자른 이후에도 나무는 0부터 다시 자라기 때ㅜㅁㄴ에 같은 나무를 여러 번 자를 수 있다.
  
  
• 나무 : 1번부터 n번
• 다음 줄에는 첫날 올라갔을 때 나무의 길이
• 나무들이 자라는 길이
  
  
• 나무를 잘라서 구할 수 있는 최대 양

 

풀이

• 나무의 수 : n → n일 동안 산을 오르면서 나무를 잘라나갈 것
• 하루에 성장할 수 있는 길이가 가장 긴 나무를 제일 마지막에 자르는 것이 잘라가는 나무 길이의 최대 값을 얻을 수 있는 방법
• 하루에 성장할 수 있는 길이가 가장 긴 나무를 제일 마지막 날에 자른다면, 그 전날에는 어떤 나무를 잘라야 하는가?
  
  
• 하루에 성장할 수 있는 나무의 길이들을 정렬해서 세웠을 때, 끝에서 두번째 나무를 잘라야 한다.
• n-1 일까지 가장 많이 나무를 성장시킨 후 자르려면 n-1번째로 성장 길이가 큰 나무를 잘라야 한다.
• 이렇게 매 순간 최적의 해를 선택하는 것이 최종적으로 최적의 정답을 만들어내는 그리디 알고리즘이다.
• 제일 마지막날 자를 나무 : 가장 많이 성장한 나무
• 최적의 해를 선택하는 과정을 역순으로 매일 진행 → 최적의 해

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 

• 하루에 성장할 수 있는 길이가 짧은 나무를 기준으로 잘라야 한다.
• 하루에 성장할 수 있는 나무의 길이를 기준으로 정렬
  
  
• 이후 1일부터 n일까지 나무를 순차적으로 자른다.
• 이때 획득할 수 있는 나무의 양은 초기 나무 길이 + i일까지의 성방분 (i * 하루 성장 길이)

 

정답 코드

import sys
input = sys.stdin.readline

n = int(input())
height = list(map(int, input().split()))
growth = list(map(int, input().split()))

# 자라는 길이에 대해 정렬
trees = []
for i in range(n) :
    trees.append([growth[i], height[i]])

trees.sort() # 자라는 길이에 대해 정렬

ans = 0
# n-1 일부터 첫날까지
for i in range(n) :
    ans += trees[i][1] + trees[i][0] * i
print(ans)