Algorithm, boj, 합분해(2225)

풀이

• dp[i][j] : j개를 사용해서 i를 만들수 있는 경우의 수
• arr[0] + arr[1] + arr[2] + … + arr[j] => 는 할때마다 더하지 말고, 메모이제이션 기법을 사용해서 더해놓자.dp[i-1][j]로 도출할 수 있다.

소스

package org.baekjoon;

import java.util.Scanner;

public class test2225_dp {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();

		// 0~n까지 더해서 k를 만든다
		int[][] dp = new int[N+1][K+1];

		for (int i=0; i<N+1; i++) {
			for (int j=1; j<K+1; j++) {
				if (i == 0 || j == 1) dp[i][j] = 1;
				else if (j==2) dp[i][j] = i+1;
				else dp[i][j] = dp[i][j-1] + dp[i-1][j];

				dp[i][j] %= 1000000000;
			}
		}
		System.out.println(dp[N][K]);
	}

}

---

Reference

• 문제보러가기

---