[白俊]225:合分解
8071 ワード
質問する
問題を解く
N=1の場合、整数KにNを加えた場合の数は以下のようになる.
k = 1 -> 1
- dp[1][1] = 1
k = 2 -> 0 + 1, 1 + 0
- dp[1][2] = 2
k = 3 -> 0 + 0 + 1, 0 + 1 + 0, 1 + 0 + 0
- dp[1][3] = 3
dp[1][i] = i
K=1の場合、整数NはNプラス1のみとなります.
dp[i][1] = 1
dp[N][K]
−K−1個を用いてNを作る方法に0を加えるとK個を用いたのと同じであり、dp[N][K−1]の場合は個数を加える.
−K個を用いてN−1を作成する方法に1を加えるとNになる.
dp[N-1][K]の場合、個数を加算できます.
dp[N][K] = dp[N][K-1] + dp[N-1][K]
コード#コード#
import java.util.Scanner;
public class ANS2225 {
static int N, K;
static long dp[][];
static int mod = 1000000000;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
K = sc.nextInt();
//dp선언 및 초기화
dp = new long[N+1][K+1];
for(int j = 1 ; j <= K; j++){
dp[1][j] = j;
}
for(int i = 1; i <= N; i++){
dp[i][1] = 1;
}
for(int i = 2 ; i <= N; i++){
for(int j = 2 ; j <= K; j++){
dp[i][j] = (dp[i][j-1] + dp[i-1][j])%mod;
}
}
System.out.println(dp[N][K]);
}
}Reference
この問題について([白俊]225:合分解), 我々は、より多くの情報をここで見つけました https://velog.io/@kdmstj/백준-2225-합분해テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol