(Kotlin) 백준 18427 - 함께 블록 쌓기

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

18427번: 함께 블록 쌓기

풀이

N명의 학생이 최대 M개의 블록을 갖고 있으며, 각자가 갖는 블록들의 높이는 모두 다르다. 이 때, 학생 당 최대 하나의 블록을 사용해서 높이가 H인 블록을 쌓는 방법은 몇 가지가 있을지 찾는 문제이다.

1) 완전 탐색

먼저 모든 경우의 수를 계산하는 완전 탐색을 생각해볼 수 있다. 하지만 시간 복잡도가 n x n x n ... x n = O(n^m)인 지수 시간 복잡도가 나오므로 모든 경우의 수를 고려하는 방법은 불가능하다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 10)

2) 다이나믹 프로그래밍

어떻게 풀 수 있을까? 모든 경우의 수를 따져야할 것 같은데 시간이 비정상적으로 길어진다. 이 때 다이나믹 프로그래밍을 생각해볼 수 있는 것 같다. (느낌적인 느낌)

 

점화식을 어떻게 세울 수 있을까? 이 문제는 배낭문제와 유사한데, 블록을 쌓는 모든 방법을 2가지 경우의 수로 나눠서 생각해볼 수 있다. (1)임의의 [i]번째 학생의 블록을 사용하지 않고 블록을 쌓는 방법과 (2)[i]의 블록을 반드시 사용해서 블록을 쌓는 방법. 이것을 점화식으로 연결해서 생각해보면 다음과 같은 점화식이 나온다.

DP[i][0] = 1
DP[i][h] = DP[i-1][h]   , if ( h < h[i] )
DP[i][h] = (1)DP[i-1][h] + (2)DP[i-1][ h - h[i] ]    (h[i]: i번째 학생의 블록의 높이)

 

DP[i][h]는 i번째 학생까지 확인했을 때, 높이 h인 블록을 쌓는 경우의 수를 의미한다.

 

식 (2)는 [i]번째 학생의 블록을 반드시 사용하는 경우인데, 이는 높이 h에서 [i]가 사용한 블록의 높이를 뺀 높이의 블록을 [1~(i-1)] 번째 학생들의 블록만으로 쌓는 경우의 수와 같다.

사실 학생들마다 여러 블록을 가지고 있기 때문에, 식을 좀 더 정확히 표현하면

DP[i][h] = (1)DP[i-1][h] + (2)sum(DP[i-1][ h - h[i] ])이 된다.

 

DP[i][0] = 1인 이유는, 학생[i]의 블록을 반드시 사용할 때 h - h[i] = 0이라면 그 블록 하나만으로 쌓는 경우의 수 한 가지를 고려해줘야 하기 때문이다. 1로 초기화하지 않으면 dp를 진행해도 모든 값이 0으로 나온다. 

 

이를 따라서 백준의 예시 입력을 dp 테이블로 작성하면 다음과 같다.

높이(h)->	0	1	2	3	4	5
X	1	0	0	0	0	0
학생1	1	0	1	1	0	1
학생2	1	0	1	2	0	3
학생3	1	1	2	4	3	6

 

우리가 원하는 정답은 DP[n][h]인데, 이를 알기 위해서는 i=0, h=1일 때의 값부터 알아야 한다. 재귀함수와 메모이제이션 기법을 사용할 수 있지만, 나는 바텀업 방식을 사용했다.

 

위 점화식을 코드로 나타내면 아래와 같다.

// dp(점화식) 진행
for (i in 1..n){
    for (h in 1..height){
       var sum = 0
       
       // 학생들이 여러개의 블록을 갖고 있으므로 각 블록마다 식을 적용해서 합을 구한다.
       // sum(DP[i-1][ h - h[i] ])
        blocks[i].forEach { eachBlock ->
            if (h >= eachBlockt){
                sum += dp[i-1][h - eachBlock]
                sum %= 10007
            }
        }
        
        dp[i][h] = dp[i-1][h] + sum	// DP[i][h] = (1)DP[i-1][h] + (2)sum(DP[i-1][ h - h[i] ]) 
        dp[i][h] %= 10007
    }
}

코드

fun main() {
    var n = 0
    var maxBlock = 0
    var height = 0

    readLine()!!.split(" ").also {
        n = it[0].toInt()
        maxBlock = it[1].toInt()
        height = it[2].toInt()
    }

    val blocks = Array(n+1){ mutableListOf<Int>() }		// 각 학생들의 블록 배열
    val dp = Array(n+1){ Array(height+1){0} }		// dp 테이블

    // 학생들의 블록 입력 받아서 추가
    for (i in 1..n){
        dp[i-1][0] = 1
        readLine()!!.split(" ").forEach {
            blocks[i].add(it.toInt())
        }
    }

    // dp(점화식) 진행
    for (i in 1..n){
        for (h in 1..height){
            var sum = 0
            
           // 학생들이 여러개의 블록을 갖고 있으므로 각 블록마다 식을 적용해서 합을 구한다.
           // sum(DP[i-1][ h - h[i] ])
            blocks[i].forEach { eachBlock ->
                if (h >= eachBlockt){
                    sum += dp[i-1][h - eachBlock]
                    sum %= 10007
                }
            }
            
            dp[i][h] = dp[i-1][h] + sum	// DP[i][h] = (1)DP[i-1][h] + (2)sum(DP[i-1][ h - h[i] ]) 
            dp[i][h] %= 10007
        }
    }

    println(dp[n][height])
}

리뷰

• 10007로 나누는 거 처음에 까먹고 틀렸다..ㅋ
• 내 머리론 dp가 직관적으로 이해가 쉽진 않다. 가장 이해하기 어려웠던 건 i번째 학생을 고려할 때 왜 특정 학생으로 계산을 하느냐는 것이었다. 어떤 학생이든 될 수 있는데 왜 특정 학생으로 계산을 하는건지 이해가 안됐는데, 지금껏 이해한 바로는 "결국 n번째까지 가면서 모든 학생을 고려하기 때문에 순서는 상관 없다" 이다. 맞나?ㅋㅋ
• dp가 재귀와 관련돼서인지 이해하기가 어렵다. 이전 항과의 관계를 중심으로 논리적으로 이해하는 게 정신 건강에 좋을듯 하다!