[BOJ/GoldIV] 18427. 함께 블록 쌓기 - JAVA 자바

18427번: 함께 블록 쌓기

• 132ms
• DP, knapsack

N명의 학생들이 가지고 있는 블록으로 H 높이를 만들 수 있는 경우의 수를 계산하는 문제이다.

 

이 문제의 핵심은 다음과 같다

1. 한 학생당 최대 1개의 블록만 사용가능
2. 블록을 사용하지 않아도 됨

3명의 학생이 다음과 같은 높이의 블록을 가지고 있을 때 높이 1부터 h=5까지 만들 수 있는 경우의수를 생각해보자

2 3 5
3 5
1 2 3

	1	2	3	4	5
1	0	1	1	0	1
2
3

첫 번째 학생은 가지고 있는 블록으로 2, 3, 5 높이를 만들 수 있다.

 

	1	2	3	4	5
1	0	1	1	0	1
2	0	1	2	0	3
3

두번째 학생이 가지고 있는 블록은 3, 5이다.

 

두 번째 학생일 때, 높이 3을 만들 수 있는 경우는 자신이 가지고 있는 높이 3 블록1 + 이전 학생이 높이 3을 만들 수 있는 경우의 수 1 로 2 가된다

 

높이 5일 때,  이전 학생이 높이 5 - 3 = 2 를 만들 수 있는 경우의 수 1 + 자신이 가지고 있는 높이 5 블록 1 + 이전 학생이 높이 5를 만들 수 있는 경우의 수 1 = 3 이 된다. 이전 학생이 높이 2를 만들 수 있는 경우가 있다면 가지고 있는 블록 3을 이용하여 5를 만들 수 있다.

 

	1	2	3	4	5
1	0	1	1	0	1
2	0	1	2	0	3
3	1	3	4	3	6

세번째 학생이 가지고 있는 블록은 1, 2, 3이다.

 

높이 3을 만들 때, 이전 학생이 높이 3 - 1 = 2 를 만들 수 있는 경우의 수1 + 이전 학생이 높이 3 - 2 = 1 을 만들 수 있는 경우의 수0 + 자신이 가지고 있는 높이 3 블록1 + 이전 학생이 높이 3를 만들 수 있는 경우의 수 2 = 4 가 된다.

 

높이 5를 만들 때, 이전 학생이 높이 5 - 1 = 4 를 만들 수 있는 경우의 수0 + 이전 학생이 높이 5 - 2 = 3 을 만들 수 있는 경우의 수2 + 이전 학생이 높이 5 - 3 = 2 를 만들 수 있는 경우의 수1 + 이전 학생이 높이 5를 만들 수 있는 경우의 수 3 = 6 이 된다.

 

따라서 점화식을 세우면 다음과 같다.

1번. j 높이의 블록을 내가 가지고 있는지 → 가지고 있다면 + 1
2번. 이전 학생이 j - (내가 가진 블록의 높이)까지 만들 수 있는 경우의 수
3번. 이전 학생이 j 높이까지 만들 수 있는 경우의 수

i학생이 j 높이의 블록을 만들 수 있는 경우는 위의 경우를 모두 더한 값이 된다.

for (int i = 1; i <= n; i++) {
            // i 번 학생이 j 높이를 만들 수 있는지 
            for (int j = 1; j <= h; j++) {
                for(int block : list[i]) {
                    if( j == block ) dp[i][j]++; // 1번
                    if(j > block) 
                        dp[i][j] += dp[i-1][j-block]; // 2번
                }
                dp[i][j] += dp[i-1][j]; // 3번
                dp[i][j] %= 10007;
            }
        }

 

#소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	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());

		List<Integer>[] list = new ArrayList[n + 1];

		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());
			list[i] = new ArrayList<Integer>();
			while (st.hasMoreTokens())
				list[i].add(Integer.parseInt(st.nextToken()));
		}

		int[][] dp = new int[n + 1][h + 1]; // dp[i][j]: i번 학생이 j 높이를 만들 수 있는 경우의 수 저장


		for (int i = 1; i <= n; i++) {
			// i 번 학생이 j 높이를 만들 수 있는지 
			for (int j = 1; j <= h; j++) {
				for(int block : list[i]) {
					if( j == block ) dp[i][j]++; // 1번
					if(j > block) 
						dp[i][j] += dp[i-1][j-block]; // 2번
				}
				dp[i][j] += dp[i-1][j]; // 3번
				dp[i][j] %= 10007;
			}
		}
		
		System.out.println(dp[n][h]);
	}
}