백준 18427번 <함께 블록 쌓기>

백준 알고리즘 18427번

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

18427번: 함께 블록 쌓기

---

18427번

1번부터 N번까지 학생들이 각각 블록을 갖고 있다. 학생마다 최대 M개의 블록을 가질 수 있고 한 명의 학생이 가지고 있는 모든 블록의 높이는 서로 다르다.

이때, 1번부터 N번까지의 학생들이 가진 블록을 차례로 사용해 바닥에서부터 쌓아올려 하나의 탑을 만들고자 한다.

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

높이가 정확히 H인 탑을 만들 수 있는 경우의 수를 계산하여라.

 

입력으로 첫 줄에 학생의 수 N과 학생이 가질 수 있는 최대 블록의 개수 M, 탑의 높이 H가 주어진다.

그 다음 N개의 줄에 걸쳐 각 학생이 가진 블록들의 높이가 공백을 기준으로 구분되어 주어진다.

 

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

---

문제 해결

10,007로 나눠야 한다는 것을 보고 뭔가 dp일 것 같았다.

 

그래서 dp 배열을 어떻게 정의할 수 있을지 생각해봤다.

 

dp[i][j] : i번 학생까지의 블록을 사용했을 때, j를 만들 수 있는 경우의 수

따라서 dp 배열은 int[학생의 수][H]가 된다. 

 

dp 배열의 값을 구하는 방법은 아래와 같다.

1. dp[i][0]은 항상 1이다. ( 0 + 1 = 1과 같이 자기 자신이 되는 경우를 count 해야 하기 때문에)
2. 학생 수만큼 for문(i)을 돌린다. 
   1. dp[i-1]을 복사해서 dp[i]에 넣는다.
   2. 해당 학생이 가진 숫자만큼 for문(j)를 돌린다.
      1. H까지 for문(k)를 돌린다.
         1. 만약 dp[i-1][k]가 0이면 이전에 만들어지지 않았기 때문에 볼 필요가 없다.
         2. k + numbers.get(j) 값이 H보다 크면 더 이상 볼 필요가 없다.
         3. i-1번 학생까지의 블록을 사용했을 때, k를 만들 수 있는 경우의 수만큼 k+numbers.get(j)를 만들 수 있다.

 

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class BOJ_18427 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inArr = br.readLine().split(" ");
        int N = Integer.parseInt(inArr[0]);
        int M = Integer.parseInt(inArr[1]);
        int H = Integer.parseInt(inArr[2]);
        ArrayList<Integer>[] numbers = new ArrayList[N+1];
        numbers[0] = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            numbers[i+1] = new ArrayList<>();
            inArr = br.readLine().split(" ");
            for (int j = 0; j < inArr.length; j++) {
                numbers[i+1].add(Integer.parseInt(inArr[j]));
            }
        }
        // end input

        // dp[i][j] : i번 학생의 블록까지 사용했을 때, j를 만들 수 있는 경우의 수
        int[][] dp = new int[N+1][H + 1];
        dp[0][0] = 1;   // 0은 원래 있는 거니까 1
        for (int i = 1; i < N+1; i++) {     // 학생 수만큼
            dp[i] = deepcopy(dp[i - 1]);
            for (int j = 0; j < numbers[i].size(); j++) {       // 해당 학생이 가진 블록만큼
                for (int k = 0; k <= H; k++) {      // H 까지
                    if (dp[i-1][k] == 0) continue;  // 이전에 만들 수 있는 경우의 수가 없으면 continue
                    int num = numbers[i].get(j);
                    if (num + k > H) break;     // 학생이 가진 블록과 k를 합친 높이가 H보다 크면 더 이상 볼 필요 없음
                    // k에 num을 더해서 만들 수 있음 -> dp[i-1][k] += dp[i-1][k]
                    dp[i][num + k] = (dp[i][num + k] + dp[i - 1][k]) % 10007;
                }
            }
        }
        System.out.println(dp[N][H]);
    }

    static int[] deepcopy(int[] arr) {
        int[] copy = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            copy[i] = arr[i];
        }
        return copy;
    }
}

---

결과

---