<백준> 합분해(Gold 5)
[깃허브]
[백준]
https://www.acmicpc.net/problem/2225
손으로 해결한 문제였다.
이리저리 방황을 엄청 하다가 마지막에 딱 방향을 잡아서 해결했다.
문제는 아주 간단하다.
너무 간단해서 그냥 해야했다.
덧셈의 순서가 바뀐 경우는 다른 경우고 한 개의 수를 여러 번 쓸 수 있다는 거를 보니 중복 사용에 대한 고려가 필요하다고 느꼈다.
그냥 문제를 보면서 멍때리다가 '이번에는 손으로 경우의 수를 찾아보자!'라는 생각이 들어서 메모장 들고 적어보기 시작했다.
처음에는 예제 케이스들을 가지고 시작했다.
...안 보인다!?!?!
식을 써보니까 그냥 값이 뭐가 나오는지만 알겠고 그 안의 규칙성을 찾을 수 없었다.
뭔가 중복 조합인 거 같은데 그냥 공식을 집어넣으면 원하는 값이 나오지 않았고 이 방향이 아닌가 싶어서 조합처럼 작성하며 규칙성을 찾아보려고 했다.
뭔가... 뭔가... 나올 거 같은데 보기에 불편해서 눈에 들어오지 않더라
그러다가 번쩍 DP 표가 떠올랐다.
표로 그리면 뭔가 관계성이 쉽게 보일 거 같았다.
가로는 개수, 세로는 숫자로 잡고 빈칸을 채워나갔다.
0을 1개, 2개,... 채우는 방법은 모두 1개다.
1을 1개, 2개,... 채우는 방법은 가로의 숫자와 동일한 개수다.
2를 채우는 방법은 직접 해 봤을 때 1, 3, 6, 10, 16,...이 나오더라
이걸 위의 0, 1과 비교해봤을 때 규칙성이 드디어 보이기 시작했다.
바로 dp[현재 숫자][구성 개수] = dp[현재 숫자][구성 개수 - 1] + dp[현재 숫자 - 1][구성 개수] 가 보였다!!!
왜 그런지는 코드로 작성하고 제출하면서도 잘 모르겠어서 다 푼 이후에 블로그를 돌아다니며 왜 이렇게 나오는 건지 찾아봤는데 아주 설명이 잘 된 곳을 찾았다.
거기서 말해주기를 dp[n][k] = dp[0][k - 1] + dp[1][k - 1] + ... + dp[n][k - 1] 이라는 점화식이 나오는데 이건 한 숫자를 선택하면 다른 숫자가 자동적으로 정해지기 때문이라고 했다.(내가 푼 방식으로 약간 배열 순서를 변경해서 적었다.)
그런데 뭔가 아직 나한테 보인 식과는 다른 모양이다.
좀 더 읽어보니까 dp[n - 1][k] = dp[0][k - 1] + dp[1][k - 1] + ... + dp[n - 1][k - 1]이기 때문에 점화식을 변경하면 dp[n][k] = dp[n][k - 1] + dp[n - 1][k]가 된다는 것이었다.
이제야 이해가 좀 됐다.
해당 방법으로 작성한 코드는 다음과 같다.
import java.util.StringTokenizer
fun main() = with(System.`in`.bufferedReader()) {
val st = StringTokenizer(readln())
val n = st.nextToken().toInt()
val k = st.nextToken().toInt()
val dp = Array(201) { Array(201) { 1 } }
for (i in 1..n) {
for (j in 2..k) {
dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % 1000000000
}
}
println(dp[n][k])
}