백준 2281 - 데스노트 (Kotlin)

 

백준 2281 - 데스노트 (코틀린) - Gold 4

 

문제

사악한 라이토는 기발한 방법을 이용하여 L(애칭 섊)을 살해한 뒤 데스노트를 다시 손에 넣었다.

라이토는 이제 이 노트에 n명의 이름을 적어 넣으려고 한다. 이때 다음과 같은 조건을 만족시키면서 이름을 적어 넣으려 한다.

우선, 이름을 적어 넣을 때 이미 정해진 순서대로 n명의 이름을 적어 넣어야 한다. 이름을 적을 때도, 노트를 위에서 아래로, 같은 줄에서는 왼쪽 맨 끝에서 오른쪽으로 차례로 적는다고 하자.

또한 이름을 적을 때 각 사람의 이름 사이에 빈 칸을 하나씩 두려고 한다.

한 줄을 적다가 그 줄의 끝에 한 사람의 이름이 다 들어가지 않고 잘리게 되면 반드시 새로운 줄에 이름을 써야 한다. 그

렇지 않으면 이름이 중간에 잘려서 자칫하면 두 명의 사람이 죽게 된다.

이때, 각 줄의 끝에 사용하지 않고 남게 되는 칸의 수의 제곱의 합이 최소가 되도록 하려 한다.

이를 계산할 때 제일 마지막 줄은 앞으로 이름을 적을 기회가 있으므로 계산하지 않는다.

예를 들어 노트의 폭(너비)이 20인 다음의 경우를 보자.

 

각 사람의 이름의 길이가 차례로 7, 4, 2, 3, 2, 5, 1, 12, 7, 5, 6 인 경우이다.

위와 같이 적으면 차례로 1, 10, 0칸이 남아서 제곱의 합이 101이 된다. 반면에 아래의 경우에는 5, 6, 0칸이 남아서 제곱의 합이 61이 된다.

 

---

입력

첫째 줄에 n(1 ≤ n ≤ 1,000), m(1 ≤ m ≤ 1,000)이 주어진다.

m은 노트의 가로 칸의 개수(폭, 너비)이다.

다음 n개의 줄에는 각 사람의 이름의 길이가 노트에 적어야 할 순서대로 주어진다.

각 길이는 m을 넘지 않는 자연수이다.

 

---

출력

첫째 줄에 남게 되는 칸 수의 제곱의 합의 최솟값을 출력한다.

 

---

알고리즘 분류

• 다이나믹 프로그래밍

 

---

해설

이번 문제는 다이나믹 프로그래밍(DP)를 이용하여 해결해야 한다.

 

이번 문제를 해결하기 위하여 생각해야하는 부분이 있다.

“제일 마지막 줄은 앞으로 이름을 적을 기회가 있으므로 계산하지 않는다”

이를 쉽게 해결할 수 있는 방법이 뒤에서 부터 dp를 계산하는 것이다.

 

inputs = [7, 4, 2, 3, 2, 5, 1, 12, 7, 5, 6] 의 입력이 있다고 가정하자.

 

dp[10] = 0 : dp[10] 은 무조건 마지막 문장이기에 0일 것이다.

 

dp[9] 의 경우를 생각해보자.

우선 inputs[9] = 5 를 새로운 줄에 작성한다고 생각해보자.

그렇다면 (20 - 5)^2 + dp[10] 일 것이다.

다음 경우의 수로 inputs[9]를 inputs[10] 에 이어붙이는 것이다.

inputs[9] + inputs[10] < m(20) 이기에 한 줄에 작성이 가능하다.

즉, dp[9] = 0 이 되는 것이다.

 

다음 경우로 dp[8] 을 생각해보자.

위와 마찬가지로 inputs[8] = 7 을 새로운 줄에 작성하는 경우 (20 - 7) + dp[9]

inputs[9] 에 이어붙이는 경우 (20 - 7 - 5 + 1)^ 2 + dp[10]

inputs[8..10] 을 전부 이어붙이는 경우 0

즉, dp[8] = 0 전부 이어붙이는 경우가 될 것이다.

 

다음은 dp[7] 을 생각해보자.

위와 똑같다.

inputs[7] = 12 이다. 이는 inputs[8] = 7 까지만 이어붙일 수 있다.

• inputs[7] 만 새로운 줄에 작성하는 경우 (20 - 12)^2 + dp[8]
• inputs[7] 와 inputs[8] 을 이어붙이는 경우 (20 - 12 - 7 - 1)^2 + dp[9]

즉, dp[7] = 0 두 번째 경우가 최소값이 된다.

다음으로 dp[6] 의 경우만 확인하겠다.

inputs[6] = 1 이다.

이는 inputs[7] = 12 까지만 이어붙일 수 있기에 위와 똑같은 경우의 수만 생각하면 된다.

• (20 - 1)^2 + dp[7] = 361
• (20 - 1 - 12 - 1)^2 + dp[8] = 36

dp[6] = 36 

 

마지막으로 dp[5] 의 경우만 확인해보자.

inputs[5] = 5 이므로 inputs[7] 까지 이어붙일 수 있다.

그럼 경우의 수는 아래와 같다.

• inputs[5] 만 새로운 줄 : (20 - 5)^2 + dp[6](36) = 261
• inputs[6] 까지 이어붙이기 : (20 - 5 - 1 - 1)^2 + dp[7](0) = 169
• inputs[7] 까지 이어붙이기 : (20 - 5 - 1 - 1 - 12 - 1)^2 + dp[8](0) = 0

dp[5] = 0

 

이정도면 이해가 됐을 것이라 생각한다.

1. 현재 이름을 새로운 줄에 작성하기
2. 현재 이름을 이전 줄에 작성하기 (만약 이전 줄에 작성할 수 없다면 새로운 줄에)

---

전체 코드

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

private const val INF = Int.MAX_VALUE

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (n, m) = br.readLine().split(" ").map { it.toInt() }
    val inputs = mutableListOf<Int>()
    val dp = Array(n) { INF }

    repeat(n) {
        inputs.add(br.readLine().toInt())
    }

    //뒤에서부터 탐색 시작
    for (i in n - 1 downTo 0) {
        //남은 노트 길이
        var p = m - inputs[i]

        //m을 넘지 않을 때 까지 이어붙이기
        for (j in i + 1 until n) {
            if(p < 0){
                break
            }

            //이어 붙이기 or 다른 페이지에 작성하기 비교
            dp[i] = minOf(dp[i], (p * p) + dp[j])

            p -= inputs[j] + 1
        }

        //모든 페이지를 이어붙여도 0보다 크다면 한 문장안에 작성 가능
        if(p >= 0){
            dp[i] = 0
        }
    }

    println(dp[0])
}

 

---

정답

 

 

분명 정답률이 42% 였는데 너무 어려운 문제였다.

스스로 생각해보려 노력했으나 너무 어려워 다른 사람들의 풀이를 볼 수 밖에 없었다.

다른 사람들은 대부분 재귀를 이용했으나 굳이 재귀까지는 이용할 필요는 없을 것 같아서 나는 2중 for문을 이용했다.

오히려 풀이가 재귀로 되어있어서 내게는 이해하기가 너무 어려웠다...