[Algo] 백준 18427 함께 블록 쌓기

문제 바로가기 : https://www.acmicpc.net/problem/18427

메모리 : 16836KB

시간 : 128ms

언어 : Java 11

---

코드

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

public class Main {
    public static <T> 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());
        int mod = 10007;
        int[] hight = new int[H + 1];
        hight[0] = 1;
        for (int i = 0; i < N; i++) {
            int[] block = new int[M];
            st = new StringTokenizer(br.readLine());
            int idx = 0;
            while (st.hasMoreTokens()) {
                block[idx++] = Integer.parseInt(st.nextToken());
            }
            for (int h = H; h > 0; h--) {
                for (int b : block) {
                    if(b==0) break;
                    if (h - b >= 0) {
                        hight[h] = (hight[h] + hight[h - b]) % mod;
                    }
                }
            }
        }
        System.out.println(hight[H]);

    }
}

 

풀이

일단 10007로 나눈 나머지를 답으로 요구하는 부분에서 다이나믹 프로그래밍을 짐작해 볼 수 있다. 가진 블록들을 조합해 높이를 맞추는 문제이기 때문에 베낭 알고리즘을 사용해야한다.

N번 까지의 학생들이 각각 블록을 가지고 있고, 학생들은 가진 블록을 사용하거나, 사용하지않아서 주어진 높이를 맞추어야 한다. 한 학생이 두 개의 블록을 낼 수 없다는 의미이다. hight배열을 구할 높이만큼 만들어 준 뒤 가장 높은 경우부터 탐색해준다. 왜냐하면 낮은 높이부터 탐색하면, 이미 블록을 낸 경우가 섞여들어가기 때문이다. 블록은 하나만 제출할 수 있는데 작은 블록에서 먼저 dp를 해주면 이 값이 큰 블록에 영향을 주기 때문이다. `hight[h] + hight[h - b]`를 통해 부족한 높이만큼 다른 사람이 낸 블록의 경우의 수를 더해준다.

dp는 어려워.. 이다..