[그리디/백준] 14247번 : 나무 자르기

- 문제 : https://www.acmicpc.net/problem/14247

 

문제 이해 

- n개의 나무를 n일에 걸쳐서 하나씩 자른다 

- i번째 나무를 한번 자르면 다음날에 grow_term[i]만큼 자란다

- 위의 방법대로 나무를 n일 동안 잘랐을 때 나무 길이의 최대값을 구한다

 

풀이 팁

- 하나의 나무를 나눠서 자르는 것보다 한 번에 나무 전체를 다 자르는 것이 효율적이다. (어차피 나무들이 1일마다 grow_term[i]만큼씩 자라기 때문)

- 따라서 자를 나무 순서를 정한 뒤 그 순서대로 자르면 자른 나무 길이의 합이 최대가 된다. 

- 나무 순서 정하는 방법은 성장세가 낮은 나무, 즉 grow_term[i]의 값이 작은 값부터 베면 된다. 

 

풀이 로직 

- 나무 순서와 grow_term 간에 관계가 있으므로 result 배열에 리스트로 [나무 초기 길이, grow_term 값]을 넣고

- grow_term을 기준으로 result를 오름차순 정렬한다. 

- 0일부터 n - 1일까지 반복문을 돌면서 i일에 해당하는 나무의 길이(초기값(result[i][0]) + 며칠(i) * 증가값(result[i][1])를 answer에 누적한다.

 

- 정답 풀이 

n = int(input())
first = list(map(int, input().split()))
grow_term = list(map(int, input().split()))

result = []
for i in range(len(first)):
    result.append([first[i], grow_term[i]])
    
result.sort(key = lambda x : x[1])
    
answer = 0    
for i in range(len(result)):
    answer += i * result[i][1] + result[i][0]
    
print(answer)