BOJ_18427_함께 블록 쌓기 (Java)

[Gold IV] 함께 블록 쌓기 - 18427

문제 링크

성능 요약

메모리: 17560 KB, 시간: 160 ms

분류

다이나믹 프로그래밍, 배낭 문제

제출 일자

2025년 1월 21일 20:14:25

문제 설명

1번부터 N번까지의 학생들은 각각 블록들을 가지고 있다. 학생마다 최대 M개의 블록을 가지고 있을 수 있으며, 한 명의 학생이 가지고 있는 모든 블록들의 높이는 서로 다르다. 이 때 1번부터 N번까지의 학생들이 가진 블록을 차례대로 사용하여 바닥에서부터 쌓아올려 하나의 탑을 만들고자 한다.

단, 어떤 학생의 블록은 사용하지 않아도 되며 한 학생당 최대 1개의 블록만을 사용할 수 있다.

1번부터 N번까지의 학생들이 가지고 있는 블록들에 대한 정보가 주어졌을 때, 높이가 정확히 H인 탑을 만들 수 있는 경우의 수를 계산하는 프로그램을 작성하시오.

예를 들어 N=3, M=3, H=5일 때, 각 학생마다 가지고 있는 블록들의 높이가 다음과 같다고 가정하자.

• 1번 학생: 2, 3, 5
• 2번 학생: 3, 5
• 3번 학생: 1, 2, 3

이 때, 탑의 높이가 정확히 5가 되도록 블록을 쌓는 경우로는 다음의 6가지가 존재한다. (블록을 사용하지 않는 경우는 X로 표시하였다.)

입력

첫째 줄에 자연수 N, M, H가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 10, 1 ≤ H ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 각 학생이 가진 블록들의 높이가 공백을 기준으로 구분되어 주어진다.

단, 모든 블록의 높이는 1,000 이하의 자연수이며 한 명의 학생이 가지고 있는 모든 블록들의 높이는 서로 다르게 주어진다.

출력

첫째 줄에 높이가 H인 탑을 만드는 경우의 수를 10,007로 나눈 나머지를 출력한다.

문제 풀이

dp로 메모이제이션하며 모든 경우의수에 대한 개수를 세주었다.

코드

package BOJ_18427_함께블록쌓기;

/**
 * Author: nowalex322, Kim HyeonJae
 */

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

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static final int MOD = 10007;
    static int N, M, H, dp[][];
    static ArrayList<Integer>[] block;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
//        br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_18427_함께블록쌓기/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());

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

        dp = new int[N + 1][H+1];
        dp[1][0] = 1;
        for(int b : block[1]){
            if(b <= H) dp[1][b] = 1;
        }

        for(int i=2; i<=N; i++){
            for(int j=0; j<=H; j++){
                // i번째 안 쌓으면
                dp[i][j] = dp[i-1][j];

                // i번째에 쌓으면
                for(int b : block[i]){
                     // 이번에 j높이까지 쌓기위해 height를 쌓는데 이 값이 쌓기전에 높이가 음수면 말이 안됨. 쌓기전 값 최소 0 (인덱스 문제도 해결)
                    if(j-b>=0) dp[i][j] = (dp[i][j] + dp[i-1][j-b]) % MOD; // 이전것도 고려해서 더해줌
                }
            }
        }

        bw.write(String.valueOf(dp[N][H]));
        bw.flush();
        bw.close();
        br.close();
    }
}