k-1 길이의 오르막 수에서 마지막 수보다 크거나 같은 수를 이어 붙이면 길이가 k인 오르막 수를 구할 수 있다.
ex) 123 -> 1233, 1234, ..., 1239
이렇게 수의 길이 k에 대해 직전 항으로 다음 항을 만들 수 있으므로 다이나믹 프로그래밍으로 문제를 해결할 수 있다.
길이 k와 마지막 자리 숫자 i로 점화식 dp를 정의하면,
dp[k][i]: 길이가 k이고, i로 끝나는 오르막 수
dp[k][i] = sum( dp[k-1][j] ), (0 <= j <= i)
코드
fun main(){
val n = readLine()!!.toInt()
val dp = Array(n+1){IntArray(10)}
// 길이가 1이고 i로 끝나는 오르막수
for (i in 0 until 10){
dp[1][i] = 1
}
// 길이 2~n까지 n-1번 반복
for (k in 2..n){
for (i in 0..9){
for (j in 0..i){
dp[k][i] = (dp[k][i] + dp[k-1][j]) % 10_007
}
}
}
println(dp[n].toList().reduce{acc, num -> (acc + num) % 10_007})
}
길이가 (k-1)인 계단 수에 마지막 자리 숫자의 +1, -1한 수를 붙이면 길이가 k인 계단 수를 구할 수 있다.
ex) 12 -> 121, 123
이걸 점화식으로 표현하기 위해 dp[k][i]를 아래와 같이 정의하면,
dp[k][i]: 길이가 k이고, 마지막 자리 숫자가 i인 계단 수의 개수
dp[k][i] = {
if (i == 0), dp[k-1][i+1]
if (0 < i < 9), sum(dp[k-1][i+1]) + sum(dp[k-1][i-1])
if (i == 9), dp[k-1][i-1]
}
ex) 길이가 4이고 3으로 끝나는 계단 수의 개수는, 길이가 3이고 2로 끝나는 계단 수의 개수와 4로 끝나는 계단 수의 개수를 합한 값
위와 같이 계단 수의 길이를 기준으로 이전 항의 값으로 다음 항의 값을 표현할 수 있고, 키 포인트는 이전 길이의 계단 수들이 어떤 숫자로 끝났는지 기록하는 것이다. 그리고 0과 9로 끝나는 수들은 다른 숫자들과는 다르게 1과 8에서만 파생된다.
이 문제는 다이나믹 프로그래밍 유형으로, 문제 상황을 이전 값으로 다음 값을 표현할 수 있으면 해결이 가능하다. 그걸 어떻게 생각해내느냐는 어릴 때 수학을 열심히 했거나, 머리가 좋거나, 둘 다 아니라면 문제를 많이 풀어보는 수밖에 없는듯 하다.
코드
fun main(){
val n = readLine()!!.toInt()
var table = Array(100){IntArray(10)}
// 한 자리 계단 수는 1~9 한 개씩
for (i in 1..9){
table[0][i] = 1
}
// 길이 2~n까지 n-1번 반복
repeat(n-1){ k ->
table[k+1][0] = table[k][1]
table[k+1][9] = table[k][8]
for (i in 1..8){
table[k+1][i] = (table[k][i-1] + table[k][i+1]) % 1_000_000_000
}
}
// 길이 n의 모든 계단 수의 개수를 합한다
println(table[n-1].toList().reduce{acc, num -> (acc + num) % 1_000_000_000})
}
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가 재귀와 관련돼서인지 이해하기가 어렵다. 이전 항과의 관계를 중심으로 논리적으로 이해하는 게 정신 건강에 좋을듯 하다!