[파이썬/Python] 백준 14247번: 나무 자르기

📌 문제 : 백준 14247번

---

📌 문제 탐색하기

n : 나무의 개수 $(1 ≤ n ≤ 100,000)$
H : 첫날의 나무 길이들 $(1 ≤ H_{i} ≤ 100,000)$
A : 나무가 자라는 길이 $(1 ≤ A_{i} ≤ 10,000)$

밤마다 각각 다른 정도로 빠르게 자라는 나무들을 잘랐을 때 얻을 수 있는 최대 나무 양을 구하는 문제이다.

문제 풀이

⭐️ 나무 자르는 방법

• 1일 나무 → 1그루, n일 간 나무를 잘라간다.
• 나무가 자라는 길이는 각각 다르다.
• 어느 나무를 먼저 잘라가느냐에 따라 총 구할 수 있는 나무 양이 다르다.
• 자른 후 0부터 다시 자라기 때문에 같은 나무 여러 번 자를 수 있다.

1번째 아이디어

매일 제일 큰 나무를 자른다면 최대 나무 양을 얻을 수 있다고 생각했다.
예제 1로 테스트해보았을 때,
아래와 같이 출력이 56으로 최대 양을 보장하지 않는다는 것을 확인할 수 있었다.

나무	나무1	나무2	나무3	나무4	나무5
자라는 양	2	7	3	4	1

날짜	나무1	나무2	나무3	나무4	나무5	총 나무 양
1	1	3	2	4	6	0
자른 후	1	3	2	4	0	6
2	3	10	4	8	0	6
자른 후	3	0	4	8	0	16
3	5	7	8	12	2	16
자른 후	5	7	8	0	2	28
4	7	14	11	4	3	28
자른 후	7	0	11	4	3	42
5	9	7	14	8	4	42
자른 후	9	7	0	8	4	56

2번째 아이디어

n일이 지난 후 가장 적게 자리는 나무를 먼저 자르고,
마지막 날에 최대로 자란 나무를 자른다면 최댓값을 얻을 수 있지 않을까라고 생각했다.

첫날 나무 길이와 하루에 자라는 양을 튜플로 묶고, 자라는 양을 기준으로 정렬한다.
자라는 양 순서대로 매일 해당 나무를 자르고 총합을 확인한다.

나무	나무1	나무2	나무3	나무4	나무5
자라는 양	1	2	3	4	7

날짜	나무1	나무2	나무3	나무4	나무5	총 나무 양
1	6	1	2	4	3	0
자른 후	0	1	2	4	3	6
2	1	3	5	8	10	6
자른 후	1	0	5	8	10	9
3	2	2	8	12	17	9
자른 후	2	2	0	12	17	17
4	3	4	3	16	24	17
자른 후	3	4	3	0	24	33
5	4	6	6	4	31	33
자른 후	4	6	6	4	0	64

원하는 값을 얻을 수 있었다.
따라서 자라는 양을 오름차순 정렬 후 그 순서대로 나무를 자르는 방법으로 구현해보았다.

가능한 시간복잡도

자라는 양 기준으로 나무 오름차순 정렬 → $n log(n)$
for문으로 n만큼 돌면서 자른 나무 양 누적합 계산 → $O(n)$

최종 시간복잡도
$n log(n)$으로 최악의 경우 $10^5 * log(10^5)$으로 2초 내에 계산이 가능하다.

알고리즘 선택

자라는 나무 길이 기준으로 정렬 후, 자라는 양이 작은 나무부터 누적합에 더하면서 총 나무 양 계산하기

---

📌 코드 설계하기

1. n 입력
2. H 입력
3. A 입력
4. 나무 첫날 길이, 자라는 양 튜플로 묶기
5. 자라는 양 기준으로 나무 리스트 오름차순 정렬
6. 자른 나무 길이 저장할 변수 정의
7. 적게 자라는 나무 길이부터 누적합 계산
8. 정답 출력
   
   

---

📌 시도 회차 수정 사항

1회차

---

📌 정답 코드

import sys

input = sys.stdin.readline

# n 입력
n = int(input())

# H 입력
H = list(map(int, input().split()))

# A 입력
A = list(map(int, input().split()))

# 나무 첫날 길이, 자라는 양 튜플로 묶기
tree = []
for i in range(n):
    tree.append((H[i], A[i]))

# 자라는 양 기준 정렬
tree.sort(key=lambda x: x[1])

# 자른 나무 길이 저장할 변수 정의
cut_tree = 0

# 적게 자라는 나무 길이부터 누적합 계산
for day in range(n):
    h, a = tree[day]
    cut_tree += h + a * day

# 정답 출력
print(cut_tree)

• 결과