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

 

 

 

문제 출저

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

18427번: 함께 블록 쌓기

 

 

 

문제 풀이

학생이 가진 블록을 하나만 사용할 수 있다. 같은 학생의 블록들을 중복 사용하지 않도록 주의해야 합니다.

그 외에는 높이 h 크기인 1차원 int 배열을 사용하여 메모리제이션을 사용해서 문제를 풀었습니다. 

 

int[] before = new int[h+1];

int[] after = new int[h+1];

 

두 개의 1차원 int 배열을 사용합니다. before는 경우의 수를 세기 전 상태, after는 경우의 수를 센 후 상태 입니다. 

before와 after 두 개의 배열 사용하는 이유는 같은 학생의 블록들의 중복 사용을 방지하기 위해서 입니다. 

 

학생이 가진 블록들을 이용해 경우의 수를 계산합니다. 점화식은 다음과 같습니다. 

 

1. after[number] += 1; (학생이 가진 블록의 크기에 +1을 한다. )

2. if(j - number >= 0) after[j] += before(j - number); (현재 탐색하는 탑의 높이 j의 지금 탐색하는 블록의 높이를 뺀 곳에 경우의 수를 더한다.)

 

이런 식으로 DP 배열을 업데이트하여 정답을 구합니다.

문제의 조건대로 정답에 % 10007로 나눈 나머지를 출력합니다.

 

 

 

 

소스 코드

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

/*
함께 블록 쌓기
https://www.acmicpc.net/problem/18427

한 학생당 최대 1개의 블록만 사용할 수 있다.

전과 결과가 있어야 한다.

2% 오답
정답 출력 부분에 % 10007을 추가하여 해결

 */

public class Main {

    static int n; // 학생 수
    static int m; // 최대 블록 종류 수
    static int h; // 목표 높이
    static List<Integer>[] blocks;

    static int[] before;
    static int[] after;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        h = Integer.parseInt(st.nextToken());

        blocks = new List[n];
        for (int i = 0; i < n; i++) {
            blocks[i] = new ArrayList<>();
        }

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            while(st.hasMoreTokens()) {
                blocks[i].add(Integer.parseInt(st.nextToken()));
            }
        }

        before = new int[h+1];
        after = new int[h+1];

        for (int i = 0; i < n; i++) {


            for (int number : blocks[i]) {

                after[number] += 1;

                for (int j = 0; j < h+1; j++) {
                    if (j - number >= 0) {
                        after[j] += (before[j - number]) % 10007;
                    }
                }

            }

            for (int j = 0; j < h+1; j++) {
                before[j] = after[j];
            }

        }

        System.out.println(before[h] % 10007);

    }

}