[백준 2225번] 합분해 - java

문제 설명

1. 0부터 N까지의 정수 K 개를 더해서 합이 N이 되어야 한다.

2. 즉 N번 계산해서 K가 나오도록

 

풀이 과정

 1. 이거 DP이다.

 2. DP는 일단 무식하게 풀면서 점화식을 찾아보는 것이 중요하다.

 3. 그래서 풀어보면

요런 식으로 나온다.

한번 계산할 때에는 (0) | (1) | (2) | (3) | (4)

두번 계산할 때에는 (00) | (10) (01) | (03) (12) (21) (30) | (04)(13)(22)(31)(40)

이런 식으로 간다.

 

그래서 저거 잘 들여다 보면 점화식이 대충 보인다.

val[i][j] = val[i-1][[j] + val[i][j-1]

이런 식으로

 

그래서 일단 전체를 1로 초기화하고 더해가면 된다.

 

코드

import java.util.*;

public class Main
{
  
	public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    
    long MODULAR = 1000000000;
    
    int N = sc.nextInt();
    int K = sc.nextInt();
    
    long val[][] = new long[K+1][N+1];
    
    for (int i=0; i<K+1; i++) {
      for (int j=0; j<N+1; j++) {
        val[i][j] = 1;
      }
    } 
    
    for (int i=2; i<K+1; i++) {
      for(int j=1; j<N+1; j++) {
        val[i][j] = (val[i-1][j] + val[i][j-1]) % MODULAR;
      }
    }
    
    System.out.println(val[K][N]);
  }
}