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

 

백준 14247

 

 

 

문제

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

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

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

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

입력

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

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

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

출력

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

제한

•  1≤n≤100000$1≤n≤100\,000$ 
•  1≤Hi≤100000$1≤H_i≤100\,000$ 
•  1≤Ai≤10000$1≤A_i≤10\,000$ 

예제 입력 1 복사

5
1 3 2 4 6
2 7 3 4 1

예제 출력 1 복사

64

 

 

 

 

---

그리디 알고리즘

 

 

하루에 1개 총 n개의 나무를 벨 수 있으므로

자라는 속도가 가장 빠른 나무를

맨 마지막에 자를수록 유리하다.

 

 

즉, speed 를 기준으로 정렬을 해놓고

하루씩 차례대로 나무를 베어주면 된다.

 

 

시간복잡도는 O(n), 공간복잡도는 O(1)

 

 

 

 

import sys 

N = int(sys.stdin.readline())

heights = list(map(int, sys.stdin.readline().split()))
speeds = list(map(int, sys.stdin.readline().split()))

arr = []
for i in range(N):
    arr.append([speeds[i],heights[i]])

arr.sort()

ans = 0

for i in range(N):
    ans += arr[i][0]*i + arr[i][1]
    
print(ans)