경우의 수 문제라서 일단 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]);
}