백준 14247번 파이썬 문제풀이(나무 자르기)

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

14247번: 나무 자르기

---

그리디 문제이나 그리디 문제들 특징이 처음보면 생각해내기가 쉽지않다는 것이다.

 

해당문제도 "참고로, 자른 이후에도 나무는 0부터 다시 자라기 때문에 같은 나무를 여러 번 자를 수는 있다." 이 지문때문에 난이도가 상승하는데 사실 이지문이 있어도 모든 나무를 한번씩 자르는 것이 최대 이득이다.

왜냐하면 어차피 나무들은 냅두면 계속 자라기 때문에 가장 적게 자라는 나무부터 오름차순으로 계속 베어가면 마지막에 최대 길이로 자란 나무를 잘랐다고 했을 때(그 나무는 5일치 만큼 성장해있을 테니) 얻을 수 있는 만큼의 최대 나무 길이를 얻었다고 할 수 있다.  

 

N = int(input())

trees = list(zip(map(int, input().split()), map(int, input().split())))

trees.sort(key=lambda x: (x[1], x[0]))  # 1. 성장하는 길이만큼, 2. 초기 나무길이 만큼 오름차순 정리

ans = 0
for i in range(N):
    ans += (trees[i][0] + (i * trees[i][1])) # 초기 나무길이 + (성장한 날짜 * 성장하는 길이)

print(ans)