백준 142471 [Kotlin, S2] 백준 14247번 나무 자르기 나무 자르기(14247번)Silver 2#그리디 알고리즘 #정렬 문제 내용 문제 접근n일 동안 나무를 잘라서 얻을 수 있는 나무의 최대 양을 구한다.첫날의 나무는 n개의 나무가 각각 h의 높이를 이루고 있고 날이 지날 때마다 hⁱ 에 해당하는 aⁱ 만큼 나무가 자라게 된다. 문제를 보면 날마다 자라는 나무의 높이가 다르기 때문에 매일 제일 높이가 높은 나무를 고르는 것으로 문제를 해결할 수 있다고 생각하기 쉽다.하지만 그 방법은 최적해가 아니다. 우리는 제일 덜 자라는 나무부터 시작해서 제일 잘 자라는 나무 순서대로 나무를 골라야 한다.나무가 잘 자랄수록 나중 갈수록 나무의 높이가 매우 커지기 때문에 매일 제일 높이가 높은 나무를 고르는 것보다 더 많이 나무를 고를 수 있데 된다. 이제 이 아이디어를 .. 2025. 1. 14. 이전 1 다음 728x90 반응형
