[BOJ/python] 14247번 나무 자르기

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

14247번: 나무 자르기

 

 

문제 해석

 

n개의 나무가 존재한다. 하루에 한그루씩 n일동안 나무를 잘라 얻을 수 있는 최대 길이를 구하는 문제이다.

---

코드

input = __import__('sys').stdin.readline
n = int(input())
arr = []
ans = 0

a = list(map(int,input().split()))
b = list(map(int,input().split()))
for i in range(n):
    arr.append([a[i],b[i]])
    
arr = sorted(arr, key = lambda x: [x[1]])

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

print(ans)

---

문제 풀이

 

일단 가장 많은 나무를 얻으려는 조건을 2가지 생각해봤다.

1. 모든 나무를 한번씩 잘라야한다.

2. 자라나는 길이가 가장 적은 순으로 자른다.

이를 통해 가장 자라는 속도가 빠른 나무일수록 최대한 아껴서 자르면 가장 많은 나무를 얻을 수 있을것 같다고 생각했다.

 

자라나는 길이가 가장 적은순으로 정렬하기 위해 첫날의 나무의 길이와 성장길이를 묶어 2차원 배열로 저장했다.

arr = sorted(arr, key = lambda x: [x[1]])

이를 통해 성장하는 길이가 적은 순으로 2차원 배열을 정렬했다.

arr[0][0]에는 첫날의 길이, arr[0][1]에는 성장하는 길이가 저장된다.

 # example
 # [[6, 1], [1, 2], [2, 3], [4, 4], [3, 7]]

정렬된 배열은 다음과 같이 저장된다.

 

이후 for문을 통해 arr[j][0]부분을 arr[j][1] 만큼 더해가면서 ans에 arr[i][0] 값을 더하려 했는데 이는 시간복잡도가 O(n^2)이 되버려 시간초과가 나버렸다.

 

따라서 첫날의 길이 + (성장한 날 * 성장하는 길이) 를 ans 값에 더해주었다.

ans += arr[i][0] + (i * arr[i][1])

 

원문:

https://ddingmin00.tistory.com/21

[BOJ/python] 14247번 나무 자르기