[백준 알고리즘] 2225번 자바(Java) 합 분해

조건

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

 

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

풀이

아래 그림을 참고하면 이해가 쉽다. 그림은 현재 0부터 6까지의 정수 4개르 더해서 그합이 6이 되어야한다. 그것을 표로 표현하면 아래처럼된다. 규칙을 보면 주황칸2개가 빨강칸의 값이 되는것을 알 수 있고 이를 통해서dp식을 짜게되면  map[i][j] = map[i-1][j]+map[i][j-1] 이런식이 된다.여기에 추가로 그 값이 int값의 범위를 추후 벗어나기때문에 

map[i][j]값을 정의할때 %10억 해주면 된다.

 

예제 입력 예시

6 4

 

예제 출력 예시

84

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//합 분해 2225번

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        //해당 크기의 배열을 만들어주고 윗칸과 좌칸의 합이 해당 칸의 값이다.
        int N = Integer.parseInt(st.nextToken()); //x
        int K = Integer.parseInt(st.nextToken()); //y
        int[][] map = new int[K][N+1];

        for (int i = 0; i < K; i++) {
            map[i][0] = 1;
        }

        for (int i = 0; i < N+1; i++) {
            map[0][i] = 1;
        }

        for (int i = 1; i < K; i++) {
            for (int j = 1; j < N+1; j++) {
                map[i][j] = (map[i-1][j]+map[i][j-1])%1000000000;
            }
        }

        System.out.println(map[K-1][N]);
    }
}

 

 

 

 

문제 출처

https://www.acmicpc.net/problem/2225

2225번: 합분해