[백준] 18427 함께 블록 쌓기 - Java

 

 

 

다이나믹 프로그래밍 유형 문제는 dp 배열 디자인과 점화식 설정이 90%, 나머지 10%는 구현이다.

 

키보드를 치는 시간보다 종이에 배열 디자인, 점화식 구하는 시간이 훨씬 더 길다..

 

dp[i][j] : 1 ~ i 번 까지 학생이 높이가 j인 탑을 만드는 경우의 수

 

학생이 블럭을 사용하지 않는경우도 있으니 점화식은 이 부분을 고려해서 작성해야 한다.

 

dp[i][j] = dp[i-1][j] (i 번째 학생이 블럭을 사용하지 않음) + dp[i][j - list[i].get(k)] (i번째 학생이 어떤 블럭을 사용함)

 

 

 

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

public class Main {	
	static int INF = 987654321;	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int H = Integer.parseInt(st.nextToken());

		ArrayList<Integer>[] list = new ArrayList[N + 1];
		int[][] dp = new int[N + 1][H + 1];

		for(int i=1; i<N+1; i++){
			list[i] = new ArrayList<>();
			st = new StringTokenizer(br.readLine());		

			while(st.hasMoreTokens()){
				list[i].add(Integer.parseInt(st.nextToken()));
			}
		}

		for(int i=0; i<list[1].size(); i++){
			dp[1][list[1].get(i)] = 1;
		}

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

		for(int i=2; i<N+1; i++){
			for(int j=1; j<H+1; j++){
				dp[i][j] = dp[i-1][j];
				dp[i][j] %= 10007;
				for(int k=0; k<list[i].size(); k++){
					if(j - list[i].get(k) <= -1){
						continue;
					}
					dp[i][j] += dp[i-1][j-list[i].get(k)];
					dp[i][j] %= 10007;
				}
			}
		}	
	
		System.out.println(dp[N][H]);						
		
	}
}