[白俊]#2225合分解
質問する
0からNまでの整数にK個を加えてNとする場合は、プログラムを作成して個数を求めます.
加算の順序が変更されると、数が異なる場合(1+2と2+1は異なる場合)になります.1つの数を複数回使用することもできます.
入力
第1行は2つの整数N(1≦N≦200),K(1≦K≦200)を与える.
しゅつりょく
1行目の出力で答えを10000000の残りの部分に分けます.
入力例1
20 2
サンプル出力1
21
に答える
この問題はダイナミックプログラミングで解決できる.
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
int N = Integer.parseInt(input[0]);
int K = Integer.parseInt(input[1]);
long[][] dp = new long[N+1][K+1];
dp[0][0] = 1;
for(int j=1; j<=K; j++) {
for(int i=0; i<=N; i++) {
for(int l=0; l<=i; l++) {
dp[i][j] += dp[i-l][j-1];
dp[i][j] %= 1000000000;
}
}
}
System.out.println(dp[N][K]);
}
}
Reference
この問題について([白俊]#2225合分解), 我々は、より多くの情報をここで見つけました https://velog.io/@pss407/백준2225-합분해-3ym5asplテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol