[백준 | 실버2] 나무 자르기(그리디, 정렬)

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

14247번: 나무 자르기

문제

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

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

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

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

입력

첫째 줄에는 나무의 개수 n개가 있다.(1≤n≤100,000) 나무는 1번부터 n번까지 있다.

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

그 다음 줄에는 나무들이 자라는 길이 Ai가 n개가 순서대로 주어진다.(1≤Ai≤10,000)

출력

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

예제 입력 1 복사

5
1 3 2 4 6
2 7 3 4 1

예제 출력 1 복사

 

64

 

 

막 풀기

모르면 일단 정렬을 해보자

성장하는 길이를 기준으로 오름차순 정렬을 한다.(딕셔너리 저장)

같은 인덱스의 나무의 초기 길이도 함게 정딕셔너리에 저장해준다.

인덱스 : [성장길이, 초기길이]

성장길이를 기준으로 오름차순 정렬을 해준다.

날짜가 지나면서 초기 길이 + (경과한 날짜 * 성장길이)를 해줘서 누적해주었다.

 

문제풀이 개념

1. 한 나무를 여러번 자르면 손해이다.

-> n일동안 n그루의 나무를 자른다.

-> 모든 나무를 다 한번씩 자른다.

-> 나무를 자를 순서를 정한다.

 

* 어떤 나무를 먼저 자르는게 좋은가?

* 성장세가 높은 애를 나중에 팔자(주식으로 따지면 이해하기 쉬움)

2. 나중에 팔면 좋은 것 

-> 성장세가 높은 나무를 나중에 팔자.

-> 성장순서로 오름차순 정렬해서 성장세가 높은 나무를 나중에 팔자.

import sys
sys.stdin = open("20220826_백준_14247_나무자르기.txt", "r")

n = int(sys.stdin.readline().rstrip())
firstHight = list(map(int, sys.stdin.readline().rstrip().split()))
growHight = list(map(int, sys.stdin.readline().rstrip().split()))

def solution(n, firstHight, growHight) :
    dic = {}
    treeSum = 0
    day = 0

    #성장하는 속도 value [0]를 기준으로 정렬을 한다
    for i in range(n) :
        dic[i] = [growHight[i], firstHight[i]]
    
    #성장하는 속도를 기준으로 오름차순 정렬
    sordDIc = sorted(dic.items(), key=lambda x: x[1])

    #초기 나무 높이[1] + (경과 일수 * 성장하는 속도)를 더해준다.
    for key, value in sordDIc :
        grow, first = value
        treeSum += first + (grow * day)
        day += 1

    return treeSum

print(solution(n, firstHight, growHight))

# 5
# 1 3 2 4 6  <-- 처음 주어진 나무 길이
# 2 7 3 4 1  <-- 하룻마다 자랄 수 있는 나무 길이