오늘의 회고

그리디 알고리즘으로 14247번 나무 자르기 문제를 풀었다.

---

시도한 것

그때그때 큰 걸 더하자

이 생각으로 매일 자라는 나무 길이를 더하면서 가장 긴 나무를 더해갔다.
(문제에서 같은 나무를 여러 번 자를 수 있다길래)

# 그때그때 큰 걸 더하자
day = 0
cnt = 0
while True:
    if day == n: break
    if day >= 1:
        for i in range(n):
            arr[i][0] += arr[i][1]
            
    arr.sort(key = lambda x: -x[0])
    cnt += arr[0][0]
    arr[0][0] = 0

    day += 1

이렇게 풀었더니 예제도 틀렸다...

풀이

나무를 딱 한 번씩만 자르고 성장속도가 빠른 나무를 가장 나중에 자른다.

이 생각으로 알고리즘을 다시 짰더니 풀렸다.

cnt = 0
arr.sort(key = lambda x: x[1])
for i in range(n):
    cnt += arr[i][0] + arr[i][1]*i

정답 코드

import sys
input = sys.stdin.readline

n = int(input())
l = list(map(int, input().split()))
l2 = list(map(int, input().split()))
arr = [[0, 0] for _ in range(n)]
for i in range(n):
    arr[i][0], arr[i][1] = l[i], l2[i]

cnt = 0
arr.sort(key = lambda x: x[1])
for i in range(n):
    arr[i][0] += arr[i][1]*i
    cnt += arr[i][0]

print(cnt)

개선한 코드

import sys
input = sys.stdin.readline

n = int(input())
l = list(map(int, input().split()))
l2 = list(map(int, input().split()))
arr = []
for i in range(n):
    arr.append([l[i], l2[i]])

cnt = 0
arr.sort(key = lambda x: x[1])
for i in range(n):
    cnt += arr[i][0] + arr[i][1]*i

print(cnt)