[Python] 백준 14247 - 나무 자르기

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

문제

영선이는 나무꾼으로 나무를 구하러 오전에 산에 오른다. 산에는 n개의 나무가 있는데, 영선이는 하루에 한 나무씩 n$n$일 산에 오르며 나무를 잘라갈 것이다. 하지만 이 산은 영험한 기운이 있어 나무들이 밤만 되면 매우 빠른 속도로 자라는데, 그 자라는 길이는 나무마다 다르다.

따라서, 어느 나무를 먼저 잘라가느냐에 따라서 총 구할 수 있는 나무의 양이 다른데,

나무의 처음 길이와 하루에 자라는 양이 주어졌을 때, 영선이가 얻을 수 있는 최대 나무양을 구하시오.

참고로, 자른 이후에도 나무는 0부터 다시 자라기 때문에 같은 나무를 여러 번 자를 수는 있다.

입력

첫째 줄에는 나무의 개수 n개가 있다. 나무는 1번부터 n번까지 있다.

다음 줄에는 첫날 올라갔을 때 나무의 길이들 Hi가 n개가 순서대로 주어진다.

그 다음 줄에는 나무들이 자라는 길이 Ai가 n개가 순서대로 주어진다.

출력

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

 

---

풀이

랜덤마라톤을 하다가 등장한 그리디 실버딱 문제이다.

나는 안 그래도 그리디에 약하기 때문에 블로그에 풀이를 정리해보기로 한다.

 

분명 그리디 문제라고 하였다. 근데 어떻게 그리디를 쓰지?

 

충분히 생각할 수 있는 잘못된 풀이

산에 올라갈 때마다 현재 가장 길이가 큰 나무를 베어 오면 어떨까?

 

이 방법은 최적해가 되지 않는다. 초기 나무의 길이와 성장 속도에 따라 해가 영향을 받기 때문이다.

 

정답 풀이

일단 나무를 안 자른다고 가정하고, N일동안 나무가 다 자란 것이다. 그리고 나는 그 나무들을 한번에 다 자를 것이다. 분명 그게 최대가 되겠지?

그런데, 나무를 중간 중간 자르게 된다면 얻을 수 있는 나무의 총량에 손실이 생길 것이다.

 

그럼 그 손실을 최소화시키는 것이 좋을 것이다.

 

손실의 발생 정도는 (성장 속도)*(나무를 잘라버리고 난 시간)이 될 것이다.

그러면 초기 나무의 길이를 고려 안해줘도 된다!

 

나무를 잘라버리고 난 시간은 0, 1, 2, 3, .... N-1일 것이니

나무의 성장 속도를 크기가 큰 순으로 정렬한 다음 인덱스랑 곱해준 값이 최소 손실이 될 것이다.

 

그리고 전체 나무들의 길이의 합에서 그 손실을 빼주면 된다!

 

코드는 이것을 그대로 구현하면 된다.

N = int(input())
H = list(map(int, input().split())) #초기 길이들
A = list(map(int, input().split())) #매일 자라는 길이

s = 0
for i in range(N):
    s += H[i] + A[i]*(N-1)

A.sort(reverse=True)
tmp = 0
for i in range(N):
    tmp += i * A[i]

print(s - tmp)

 

앞으로 그리디를 쓸 때, 쓰지 않을 때, 그리디를 어떻게 쓸지 생각하는 연습을 조금 더 해야겠다.

역시 그리디는 어렵다.

BOJ Extented를 이용하면 이렇게 커스텀 메시지를 할 수 있더라//