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

www.acmicpc.net/problem/18427

18427번: 함께 블록 쌓기

1. 문제 설명

 

N명의 학생들이 최대 M개의 블록을 가지고, 한 학생당 최대 1개의 블록만을 사용할 수 있을 때 (사용하지 않는 경우도 가능) 높이가 정확히 H인 탑을 만드는 경우의 수를 구하는 문제.

 

2. 풀이

 

dp를 이용해서 간단하게 풀 수 있는 문제이다.

 

1번부터 X 학생까지 높이 Y인 탑을 만들 수 있는 경우의 수를 dp [X][Y]라 하고, X학생이 가진 블록을 list []에 저장하였을 때 dp [X][Y]의 값은 아래와 같다.

 

dp [X][Y]=dp [X-1][Y]+∑dp [X-1][Y-list [Z]] 

 

X학생의 블록을 사용하지 않고 높이 Y인 탑을 달성했을 경우의  수(dp [X-1][Y]), X학생의 블록 중 하나를 사용하여 높이 Y인 탑을 달성했을 경우의 수(∑dp [X-1][Y-list [Z]] )를 더해주면 된다.

 

경우의 수를 10,007로 나누는 것에 주의하여 코드를 작성하면 된다.

 

 

3. 코드

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


        // 입력
        int student_num,max_block_num,height;

        StringTokenizer num = new StringTokenizer(br.readLine());

        student_num = Integer.parseInt(num.nextToken()); // N
        max_block_num = Integer.parseInt(num.nextToken()); // M
        height = Integer.parseInt(num.nextToken()); // H

        int[][] dp = new int[student_num + 1][height + 1];




        // 풀이
        for (int x = 1; x <= student_num; x++) {

            StringTokenizer block = new StringTokenizer(br.readLine());

            dp[x - 1][0] = 1;

            int block_num = block.countTokens();

            for (int y = 0; y < block_num; y++) {

                int now = Integer.parseInt(block.nextToken());

                for (int z = now; z <= height; z++) {

                    dp[x][z] = (dp[x][z] + dp[x - 1][z - now]) % 10007;
                }

            }

            for (int k = 1; k <= height; k++) {
                dp[x][k] = (dp[x][k] + dp[x - 1][k]) % 10007;
            }

        }


        bw.write(String.valueOf(dp[student_num][height]));
        bw.close();
        br.close();


    }




}