[백준] 2225 - 합분해 (Java)

[백준] 2225 - 합분해 (Java)

문제

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

풀이/후기

dp 구조는 dp[x][y]일 때, x개를 이용하여 합이 y인 결과를 얻는 것으로 두고 짜면 된다.

점화식은 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];를 이용하여 풀이한다.

2차원 표로 생각해보면, 구하고자 하는 칸의 바로 왼쪽과 바로 윗쪽 칸의 값을 더하면 원하는 결과를 얻을 수 있다.

 

DP는 점화식만 만들면 쉽게 풀 수 있는데,

점화식을 만드는 것이 너무 어렵다!ㅠㅠㅠㅠㅠ

애초에 dp를 어떤 구조로 생각할지도 감이 잡히지 않아서

결국 검색을 해보았다.

세상엔,, 똑똑한 사람이 참 많고 난 작게 느껴진다,,ㅠㅠ

계속 반복하면서 복습해야겠다..!

코드

package DynamicProgramming;

import java.io.*;
import java.util.*;

public class Problem2225 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer str = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(str.nextToken());
		int K = Integer.parseInt(str.nextToken());

		int[][] dp = new int[K][N + 1];
		// K는 개수
		// N은 만들고자 하는 수

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

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

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

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

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/6d9a73bf98208f3d4c77a9d8171404888e939a19

참고

https://nahwasa.com/entry/%EB%B0%B1%EC%A4%80-2225-%EC%9E%90%EB%B0%94-%ED%95%A9%EB%B6%84%ED%95%B4-BOJ-2225-JAVA