18427 - 함께 블록 쌓기 (Java)

박세건·2025년 2월 5일

백준

알고리즘 문제 해결

목록 보기

3/50

📌 문제 설명

백준 18427번 - 함께 블록 쌓기

N명의 학생이 있으며, 각 학생은 M개 이하의 블록을 가지고 있음.
블록의 높이는 다양하며, 각 학생이 가진 블록 리스트가 주어짐.
학생마다 최대 한 개의 블록만 선택 가능하며, 학생 순서대로 쌓아야 함.
목표: 블록을 쌓아 높이 H를 만들 수 있는 방법의 개수를 10007로 나눈 나머지 출력.

💡 접근 방식

🔹 1️⃣ 완전 탐색 (브루트포스) → 비효율적

모든 학생이 자신의 블록을 선택하는 경우의 수를 고려해야 함.
단순 완전 탐색(DFS)으로 접근하면 최악의 경우 10^50 연산 발생 → 시간 초과 예상.

🔹 2️⃣ DFS + DP (메모이제이션) 최적화

dfs(학생 인덱스, 남은 높이)를 호출하여 각 학생이 현재 남은 높이를 만들 수 있는지 판단.
이미 계산된 dp[학생 인덱스][남은 높이] 값이 존재하면 재계산하지 않고 바로 반환.
이전 학생이 선택한 블록과 현재 학생이 선택한 블록의 조합을 고려하여 최적의 경우의 수 계산.
재귀를 사용한 방식은 Top Down 방식.

📝 코드 구현

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

public class Main {
    /*
     * 시도 1 : 모든 사람이 갖고 있는 블록을 하나의 배열에 저장
     *         (블록의 높이를 인덱스로 하여 저장, Ex: arr[1] = 2, 블록 높이 1인 블록이 2개)
     *         → 단, 이 방법은 "두 개의 블록만 사용하는 경우"만 고려되므로 실패
     *
     * 시도 2 : DFS를 사용하여 모든 경우 탐색
     *         특정 학생이 블록 `x`를 선택하면, `H - x`의 높이를 만들 수 있는지 다음 학생에게 넘김.
     *         → `O(10^50)`이므로 시간 초과 예상.
     *
     * 시도 3 : DFS + DP를 사용하여 최적화 (메모이제이션)
     *         특정 학생이 특정 높이를 만들 수 있는 경우를 한 번 탐색하면,
     *         이후 동일한 경우가 나오면 `dp` 배열을 사용하여 즉시 반환.
     *         → 해결!
     */
    
    private static StringTokenizer st;
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int N, M, H;
    private static List<Integer>[] blocks;
    private static int[][] dp;

    public static void main(String[] args) throws IOException {
        setting();
        System.out.println(dfs(0, H));
    }

    private static int dfs(int cnt, int remain) {
        if (cnt >= N) return remain == 0 ? 1 : 0; // 블록을 정확히 H 높이로 만들면 1 반환

        if (dp[cnt][remain] != -1) return dp[cnt][remain]; // 메모이제이션 활용

        int result = 0;
        for (int i = 0; i < blocks[cnt].size(); i++) {
            int cur = blocks[cnt].get(i);
            if (remain >= cur) {
                result = (result + dfs(cnt + 1, remain - cur)) % 10007;
            }
        }
        return dp[cnt][remain] = result; // 결과 저장 후 반환
    }

    private static void setting() throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());

        blocks = new List[N];
        dp = new int[N][H + 1]; // dp 배열 초기화

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

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            blocks[i].add(0); // 블록을 선택하지 않는 경우 고려
            while (st.hasMoreTokens()) {
                blocks[i].add(Integer.parseInt(st.nextToken()));
            }
        }

        // DP 초기화 (-1로 설정하여 메모이제이션 체크)
        for (int i = 0; i < N; i++) {
            Arrays.fill(dp[i], -1);
        }
    }
}

🧐 코드 분석

함수	역할
`setting()`	입력 처리 및 블록 리스트 저장
`dfs(학생 번호, 남은 높이)`	DFS 탐색 + DP를 활용한 메모이제이션
`dp[학생 번호][남은 높이]`	이전 탐색 결과 저장하여 중복 연산 방지

🚀 시간복잡도 분석

학생 수(N) ≤ 50, 블록 개수(M) ≤ 10, 목표 높이(H) ≤ 1000
DP를 활용한 탐색 (O(N * H))
- 각 dfs(학생, 남은 높이) 호출은 한 번만 계산되고 저장됨 → 최적화됨.
- 최대 50 * 1000 = 50,000 정도 연산 → 충분히 해결 가능!

🎯 결론

✅ 완전 탐색으로 접근하면 O(10^50)으로 불가능하므로 DP를 활용하여 최적화
✅ 메모이제이션(dp)을 사용하여 동일한 탐색을 피하고 O(N * H)로 해결
✅ 경우의 수를 구하는 문제는 DFS + DP를 적극 활용! 🚀

🔹 N이 더 커진다면?

현재 풀이가 O(N * H)로 최적화된 풀이이므로 추가 최적화 필요 없음.
만약 N > 1000이면 Bottom-Up DP (반복문 방식)로 변경하여 스택 오버플로우 방지 가능.

for (int i = 0; i < N; i++) {
    for (int h = 0; h <= H; h++) {
        for (int block : blocks[i]) {
            if (h >= block) {
                dp[i + 1][h] = (dp[i + 1][h] + dp[i][h - block]) % 10007;
            }
        }
    }
}