경우의 수 문제라서 일단 DP로 접근해 봤습니다.
합이 N이 되도록 정수를 배열하면,
-
마지막 수가 0인 경우
-
마지막 수가 1인 경우
-
⋯
-
마지막 수가 N인 경우
로 나뉘게 됩니다.
$f(N, K)$: 0부터 $N$까지의 정수 $K$개를 더해서 합이 $N$이 되는 경우의 수일 때 각 경우에 마지막 수가 확실히 정해지므로 $K$는 1 줄고, $N$은 마지막 수만큼 줄어듭니다.
이를 식으로 나타내면 $f(N, K) = f(N - 0, K - 1) + f(N - 1, K - 1) + \cdots + f(N - N, K - 1)$
이 식을 계산하는 데는 $O(N^2K)$ 시간이 걸립니다.
제한시간 내에 계산할 수는 있지만, 조금 더 빠르게 할 수 있습니다.
$f(N - 1, K) = f(N - 1, K - 1) + f(N - 2, K - 1) + \cdots + f(0, K - 1)$이므로 $f(N, K) = f(N, K - 1) + f(N - 1, K)$임을 이용하면 $O(NK)$에 풀 수 있습니다.
코드
use std::{
io::{stdin, Read},
mem::swap,
};
fn main() {
let mut input = String::new();
stdin().read_to_string(&mut input).unwrap();
let mut input = input.split_ascii_whitespace().map(str::parse).flatten();
let n = input.next().unwrap();
let k = input.next().unwrap();
let mut count = vec![1; n + 1];
let mut aux = vec![0; n + 1];
for _ in 1..k {
aux[0] = 1;
for i in 1..=n {
aux[i] = aux[i - 1] + count[i];
if aux[i] >= 1_000_000_000 {
aux[i] -= 1_000_000_000;
}
}
swap(&mut count, &mut aux);
}
println!("{}", count[n]);
}