[JAVA] 백준 2225번 - 합분해

2225번: 합분해 (acmicpc.net)

2225번: 합분해

package baekjoon;
import java.util.*;
import java.io.*;

public class b2225 {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		int dp[][] = new int[k+1][n+1];

		for(int i = 1 ; i <= k ; i++)
		{
			for(int j = 1 ; j <= n ; j++)
			{
				if(i == 1)
				{
					dp[i][j] = 1;
				}
				else if(j == 1)
				{
					dp[i][j] = i;
				}
				else
				{
					dp[i][j] = (dp[i-1][j] + dp[i][j-1])% 1000000000;
				}
			}
		}
		System.out.println(dp[k][n] );
	}

}

---

처음에 생각할 때 

이런 식으로 생각해서

재귀함수 쓰고 막 해야하나 했는데

dp인데? 싶어서 계속 생각하다가 구글링 해서 어떤 선생님이 하신대로 경우의 수를 표로 정리해봤는데

이렇게 되더라구요

그러면 dp[i][j] =dp[i-1][j] + dp[i][j-1] 이런 점화식을 갖게 되고

1행은 다 1이고

1열은 다 해당 행 크기만큼 갖게 돼서

for(int i = 1 ; i <= k ; i++)
		{
			for(int j = 1 ; j <= n ; j++)
			{
				if(i == 1)
				{
					dp[i][j] = 1;
				}
				else if(j == 1)
				{
					dp[i][j] = i;
				}
				else
				{
					dp[i][j] = (dp[i-1][j] + dp[i][j-1])% 1000000000;
				}
			}
		}

정리하면 이렇게 됨니다

깨달은 점...경우의 수 나열도 좋은데 경우의 수를 세서 표로 정리해보는 습관을 들여야겠다는 생각을 했습니다..

겐지충 프로그래머 :: 알고리즘 풀이 - 백준 2225(합분해, DP) (tistory.com)

알고리즘 풀이 - 백준 2225(합분해, DP)

이 선생님 글을 참고했습니다 감사합니다 선생님ㅠ ㅠ