https://www.acmicpc.net/problem/18427
18427번: 함께 블록 쌓기
첫째 줄에 자연수 N, M, H가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 10, 1 ≤ H ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 각 학생이 가진 블록들의 높이가 공백을 기준으로 구
www.acmicpc.net
풀이
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가 재귀와 관련돼서인지 이해하기가 어렵다. 이전 항과의 관계를 중심으로 논리적으로 이해하는 게 정신 건강에 좋을듯 하다!
'Problem Solving > 백준' 카테고리의 다른 글
| (Kotlin) 백준 1904 - 01타일 (0) | 2021.09.14 |
|---|---|
| (Kotlin) 백준 1744 - 수 묶기 (0) | 2021.09.02 |
| (Kotlin) 백준 1707 - 이분 그래프 (0) | 2021.09.01 |
| (Kotlin) 백준 1062 - 가르침 (0) | 2021.08.31 |
| (Kotlin) 움직이는 미로 탈출 - Gold 5 (0) | 2021.08.25 |
