[백준][그리디] 14247. 나무 자르기

14247. 나무 자르기

14247번: 나무 자르기

 

• 풀이
  • 길이가 7인 나무를 오늘 자르고, 내일 자르면 -> 14
  • 오늘 다른나무 3을 자르고, 내일 7이 더 자란 14를 자르면 -> 17
    • => 하루에 자라는 길이가 더 긴 나무를 가장 마지막까지 뒀다가 자르는게 이득

 

#하루에 한 나무씩 n일
# 하루, 하루 베어가는 길이 == 다음날 베어가는 길이
# -> 차라리 다른 나무를 베고 긴걸 다음날 베는게 더 효율적
# 자라나는 길이가 길수록 나중에
from collections import defaultdict

n=int(input())
tree=list(map(int,input().split()))
height=list(map(int,input().split()))
dic=defaultdict(list)
for idx, two_value in enumerate(zip(tree, height)):
    dic[idx].append(two_value[1])
    dic[idx].append(two_value[0])

val=list(dic.values())
val.sort()

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

print(result)