[PYTHON] 백준 14247 나무자르기

 

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

14247번: 나무 자르기

 

이 문제는 그리디 알고리즘으로 풀 수 있다.

성장속도가 제일 더딘 나무부터 빠른 나무순으로 정렬 후 베면 된다. 모든 나무를 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][1]
    for j in range(N):
        arr[j][1] += arr[j][0] 
    
print(ans)

이 풀이는 테스트케이스는 통과히지만 시간초과가 난다. 시간 제한이 2초인데 N이 100,000까지 들어올 수 있다. range(N)으로 이중 for a문을 돌렸기때문에 시간초과가 발생한다. 따라서 이중 for문을 대체할 방법을 생각해보자.. !!

 

# 백준 14247 나무자르기

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][1]
#     for j in range(N):
#         arr[j][1] += arr[j][0] -> 시간초과

for i in range(N):
    ans += arr[i][0]*i + arr[i][1]
    # 1*0 + 6
    # 2*1 + 1
    # 3*2 + 2
    # 4*3 + 4
    # 7*4 + 3
    
print(ans)

성장의 폭이 가장 작은것부터 자르고 가장 큰 나무는 N-1번 성장하게 된다. 따라서 성장값 (arr[i][0]*i)와 원래값 (arr[i][1]) 을 더해주었다.