[Kotlin, S2] 백준 14247번 나무 자르기

출처: unsplash.com

 

나무 자르기(14247번)

Silver 2

#그리디 알고리즘 #정렬

 

문제 내용

 

 

문제 접근

n일 동안 나무를 잘라서 얻을 수 있는 나무의 최대 양을 구한다.

첫날의 나무는 n개의 나무가 각각 h의 높이를 이루고 있고 날이 지날 때마다 hⁱ 에 해당하는 aⁱ 만큼 나무가 자라게 된다.

 

문제를 보면 날마다 자라는 나무의 높이가 다르기 때문에 매일 제일 높이가 높은 나무를 고르는 것으로 문제를 해결할 수 있다고 생각하기 쉽다.

하지만 그 방법은 최적해가 아니다.

 

우리는 제일 덜 자라는 나무부터 시작해서 제일 잘 자라는 나무 순서대로 나무를 골라야 한다.

나무가 잘 자랄수록 나중 갈수록 나무의 높이가 매우 커지기 때문에 매일 제일 높이가 높은 나무를 고르는 것보다 더 많이 나무를 고를 수 있데 된다.

 

이제 이 아이디어를 어떻게 구현해야 하는가?

반복문을 돌면서 가장 덜 자라는 나무를 자른 후, 나머지 나무의 높이 h에 aⁱ 만큼 더하는 과정을 반복할 수 있다.

위의 아이디어를 코드로 구현해서 제출한 결과 시간초과가 발생했다.

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val bf = BufferedReader(InputStreamReader(System.`in`))
    val n = bf.readLine().toInt()
    val h = bf.readLine().split(" ").map { it.toInt() }.toIntArray()
    val a = bf.readLine().split(" ").mapIndexed { i, data -> Pair(i, data.toInt()) }.toMutableList()
    a.sortBy { it.second }

    var answer: Long = 0
    for (i in 0 until n) {
        answer += h[a[i].first]

        for (j in a.indices) {
            h[a[j].first] = h[a[j].first] + a[j].second
        }
    }

    println(answer)
}

 

뭔가 시간 초과가 날 것 같았지만 예상대로 시간 초과가 발생했다.

내 생각에는 나무를 자른 이후에 나머지 나무를 더하는 과정이 너무 반복적이고 오래 걸리는 작업이라 시간 초과가 발생한다고 판단했다.

 

그러면 이걸 어떻게 줄이는가?

나무가 잘리는 순서를 고려하면 나무가 총 몇 번 자라는지 알 수 있는데, 이에 aⁱ 를 곱하면 반복 작업 없이 수학적으로 잘라야 하는 날에 나무의 높이를 구할 수 있게 된다.

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val bf = BufferedReader(InputStreamReader(System.`in`))
    val n = bf.readLine().toInt()
    val h = bf.readLine().split(" ").map { it.toInt() }.toIntArray()
    val a = bf.readLine().split(" ").mapIndexed { i, data -> Pair(i, data.toInt()) }.toMutableList()
    a.sortBy { it.second }

    var answer: Long = 0
    for (i in a.indices) {
        // i: 경과 날짜
        val index = a[i].first
        h[index] += (a[i].second * i)

        answer += h[index]
    }

    println(answer)
}

 

문제 풀이

우선 a를 Pair를 이용해 index, data 형식으로 값을 저장해 주었다.

index는 h와 대응하는 index를 표시하기 위해 사용한다.

data를 기준으로 오름차순 정렬을 진행해 잘리는 순서를 정의한다.

 

핵심 로직의 작동 과정만 설명해 주겠다.

 

예를 들어 다음과 같은 입력 예제가 있을 때

5
1 3 2 4 6
2 7 3 4 1

a에서 가장 작은 수는 1이고 가장 큰 수는 7이다.

아이디어에 따르면, 가장 느리게 자라는 1에 대응하는 h인 6인 나무를 시작으로 가장 빠르게 자라는 7에 대응하는 h가 3인 나무 순서대로 나무를 자르게 된다.

첫날에는 나무가 자라지 않기 때문에 aⁱ 는 사용되지 않고 두 번째 날부터 사용한다.

두 번째 날에 1번 자라게 되고 세 번째 날에는 2번 자라게 된다.

쭉 진행하면 n번째 날에는 n - 1번 나무가 성장한다.

 

이러한 원리를 파악해, hⁱ + aⁱ * 경과 날짜의 식으로 자를 때의 나무의 높이를 구할 수 있다.

h가 3인 나무가 제일 마지막 날인 다섯 번째 날에 잘리는 것을 생각한다면 4번의 성장이 있게 되기 때문에

3 + 7 * 4 = 31이 되게 된다.

 

 

문제 해결 과정

처음에는 날마다 가장 높이가 높은 나무를 자르는 것으로 생각하기 쉽다고 위에 언급했었다.

내가 실제로 그 아이디어로 입력 예제 검증을 진행했는데 정답이 다르게 나왔다.

 

가장 덜 자라는 나무부터 자르라는 아이디어는 게시판을 통해 힌트를 얻게 되었고, 코드로 구현하는 것은 크게 어렵지는 않은데

시간 초과를 고려해 식으로 나무의 높이를 구해주었다.

 

같은 나무를 여러 번 자르면 비효율적이라는 것과, 자라는 속도가 빠른 나무를 늦게 자르는 것이 이득인 것을 알게 되면 구현하는 게 어렵지는 않을 것이다.

 

체감 난이도: Silver 2