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

28 Apr 2024 in Algorithm on 다이나믹 프로그래밍

https://www.acmicpc.net/problem/18427

풀이

N명의 학생이 들고있는 블럭을 인 당 최대 한 개 사용하여 높이 H를 정확하게 맞출 수 있는 경우의 수를 구해야한다.

dp배열을 2차원으로 만들었다. new int[n + 1][h + 1]

1번 학생부터 시작하여 1~h까지 높이에 대해 경우의 수를 구한다.

n번 학생이 특정 높이 h에 대해 만들 수 있는 경우의 수는 다음과 같이 구할 수 있다.

(n번 학생이 들고 있는 h 높이의 블록의 수) + (n-1번 학생까지 했을 때 h 높이를 만든 경우의 수) + (n번 학생이 가진 a 높이의 블록 + n-1번 학생까지 했을 때 h-a 높이를 만든 경우의 수)

이 방법을 코드로 옮기면 다음과 같다.

for (int i = 1; i < n + 1; i++) {
    dp[i - 1][0] = 1;
    for (int j = 1; j < h + 1; j++) {
        for (int height : list.get(i)) {
            if (j >= height) {
                dp[i][j] += dp[i - 1][j - height];
            }
        }
        dp[i][j] += dp[i - 1][j];
    }
}

이전 번호의 높이 0의 값을 1로 초기화 해주고 진행한다.

높이 h인 블럭이 있다면 dp[i-1][j-h]의 값을 더해준다.

---

메모리: 17540KB

시간: 204ms

언어: Java 11

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        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<ArrayList<Integer>> list = new ArrayList<>();
        for (int i = 0; i < n + 1; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 1; i < n + 1; i++) {
            st = new StringTokenizer(br.readLine());
            while (st.hasMoreTokens()) {
                list.get(i).add(Integer.parseInt(st.nextToken()));
            }
        }

        int[][] dp = new int[n + 1][h + 1];

        for (int i = 1; i < n + 1; i++) {
            dp[i - 1][0] = 1;
            for (int j = 1; j < h + 1; j++) {
                for (int height : list.get(i)) {
                    if (j >= height) {
                        dp[i][j] += dp[i - 1][j - height];
                        dp[i][j] %= 10007;
                    }
                }
                dp[i][j] += dp[i - 1][j];
                dp[i][j] %= 10007;
            }
        }

        System.out.println(dp[n][h]);
    }

}