[알고리즘|파이썬] 백준 14247 나무 자르기

문제 링크: https://www.acmicpc.net/problem/14247

 

📌 문제 탐색하기

시간 제한: 2초
메모리 제한: 512 MB

 

✏️ 구해야 하는 정답

n개의 나무가 있는데, 하루에 한 나무씩 n일 산에 오르며 나무를 잘라갈 것이다. 나무들 자라는 길이는 나무마다 다르다.

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

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

조건

- 1 ≤ n ≤ 100,000

- 1 ≤ Hi ≤ 100,000

- 1 ≤ Ai ≤ 10,000

---

📌 풀이하기 

먼저 예제로 주어진 문제를 보면서 어떻게 풀지 고민을 해보도록 하자.

 

예제

5

1 3 2 4 6
2 7 3 4 1

 

현재 가장 큰 나무를 자르는 것보다, 성장 속도가 느린 나무를 먼저 자르고, 속도가 가장 빠른 나무를 가장 마지막에 자르는 것이 최대 나무를 구할 수 있는 방법이다. 

Ai = {2, 7, 3, 4, 1} 로 주어졌으므로, 나무를 자르는 순서는 5번 나무 -> 1번 나무 -> 3번 나무 -> 4번 나무 -> 2번 나무 로 정할 수 있다. 이때 일차 별로 각 나무의 현재 길이와, 영선이가 구한 나무의 길이를 표현하면 다음과 같다.

 

어떤 나무를 자를 것인가?

최적의 해를 구하기 위해 어떤 순서로 나무를 잘라야할지 생각해 보아야한다.

 

- 현재 가장 큰 나무를 자른다. (X)

- 성장률이 작은 나무부터 자른다. (= 성장률이 가장 큰 나무를 가장 마지막에 자른다) (O)

 

두 경우를 놓고 보았을때, 현재 가장 큰 나무를 잘라버리면, 성장률이 높은 나무만 계속해서 자르게 되는데, 이때 다른 나무들도 자라고 있기 때문에 이것은 최적의 해를 구할 수 있는 방법으로 볼 수 없다. 

성장률이 작은 나무부터 자른다는 것은, 성장률이 가장 큰 나무를 가장 마지막에 자른다와 동일한 뜻이다. 이렇게 되면, 성장률에 따라 가장 작은 성장률로 자란 나무를 먼저 자르고, 그 동안 자란 나무를 다음에 자르게 되면서 최적의 해를 구할 수 있게 된다.

 

현재 가장 큰 나무 자르는 경우로 문제를 풀었을 때도 비교해서 한 번 보도록 하자.

---

📌 코드 설계하기

 

1. n, h, a input을 받는다.

2. wood = 0 으로 초기화 한다.

3. tree 라는 (a, h)를 담는 배열을 만들어 sort 한다.

4. n번 만큼 돌면서 wood 값을 구하여 더한다.

5. wood 출력

---

📌 시도 회차 수정 사항

1회차: 시간 초과

n = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))
wood = 0
sorted = sorted(a)

for i in range(n):
    num = sorted[i]
    idx = a.index(num)
    wood += h[idx]
    for j in range(n):
        h[j] += a[j]
print(wood)

 

2회차: 틀렸습니다

n = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))
wood = 0
sortedA = sorted(a)

for i in range(n):
    num = sortedA[i]
    idx = a.index(num)
    wood += (h[idx] + a[idx]*i)

print(wood)

index()로 index를 찾는 경우 동일한 값이 있을때 잘못된 결과를 낼 수 있다.

 

---

📌 정답 코드

n = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))
wood = 0

trees = []
for i in range(n):
    trees.append((a[i], h[i]))
trees.sort()

for i in range(n):
    wood += (trees[i][0]*i + trees[i][1])

print(wood)