[BOJ/Java] 12422. 창문 깨기 (Large)

📌 [BOJ/Java] 12422. 창문 깨기 (Large)

🔗 문제 링크

---

📖 문제 해석

본 문제는 K개의 창문으로 둘러싸인 방에서 진행되는 상황을 모델링한다. 창문은 기본적으로 돌 한 개에 깨지나, H개의 창문은 강화되어 있어 첫 번째 돌은 견디고 두 번째 돌에 깨진다. 모임 전에 M명의 일꾼이 각각 무작위로 한 창문을 선택하여 추가 강화 작업을 수행하며, 한 번 강화할 때마다 해당 창문은 돌을 한 번 더 버틸 수 있다. 모임 당일에는 N명의 악당이 각자 한 개의 창문을 선택하여 돌을 던지며, 이미 깨진 창문에 돌이 던져지면 돌은 그대로 통과한다.

문제의 목표는 모임 후에 최소 한 개 이상의 창문이 깨질 확률을 구하는 것이다.

---

🛠️ 풀이 과정

본 문제는 각 창문의 내구성을 강화와 돌 던지기의 결과로 모델링하여, 전체 방이 안전한 상태(즉, 한 개의 창문도 깨지지 않은 상태)가 될 확률을 계산한 후, 1에서 해당 확률을 빼어 창문이 깨질 확률을 구하는 문제이다. 문제 해결 과정은 다음과 같이 진행된다.

• 창문 그룹 분리:
  K개의 창문 중 H개는 처음부터 강화된 창문(그룹 A)으로 기본 내구성이 2이며, 나머지 K − H개는 기본 창문(그룹 B)으로 기본 내구성이 1이다.
• 동적 계획법(DP)을 통한 경우의 수 계산:
  각 창문에 대해 추가 강화 횟수(dr)와 돌에 맞은 횟수(ds)의 조합으로 기여도를 계산한다. 각 창문은 다음의 안전 조건을 만족해야 한다.
  - 그룹 A(강화 창문): ds ≤ dr + 1
  - 그룹 B(기본 창문): ds ≤ dr
  각 창문에 대해 1/(dr! × ds!)의 가중치를 부여하는 생성함수를 고려하며, 전체 창문에 대한 경우의 수는 두 그룹의 DP 결과를 합성(convolution)하여 구한다.
• 최종 확률 계산:
  모임에서 총 M회의 강화와 N회의 돌 던지기가 이루어질 때, 안전한 상태의 확률 P_safe는 아래와 같이 계산된다.
  
  P_safe = (M! × N! / K^(M+N)) × S_total
  
  여기서 S_total은 전체 generating function에서 x^M·y^N 항의 계수이다. 최종적으로 창문이 깨질 확률은 1 − P_safe로 구한다.

---

💻 코드 구현 (Java)

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

public class Main {
    // M과 N의 최대값이 100임을 고려하여 MAX를 110으로 설정한다.
    static final int MAX = 110;
    
    public static void main(String[] args) throws Exception {
        // 빠른 입출력을 위하여 BufferedReader와 PrintWriter를 사용한다.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        
        int T = Integer.parseInt(br.readLine().trim());
        
        // 0부터 MAX-1까지의 팩토리얼과 로그 팩토리얼을 미리 계산한다.
        double[] fact = new double[MAX];
        double[] logFact = new double[MAX];
        fact[0] = 1.0;
        logFact[0] = 0.0;
        for (int i = 1; i < MAX; i++) {
            fact[i] = fact[i - 1] * i;
            logFact[i] = logFact[i - 1] + Math.log(i);
        }
        // 0부터 MAX-1까지의 1/n! 값을 미리 계산한다.
        double[] invFact = new double[MAX];
        for (int i = 0; i < MAX; i++) {
            invFact[i] = 1.0 / fact[i];
        }
        
        // 각 테스트 케이스를 처리한다.
        for (int t = 1; t <= T; t++) {
            String line = br.readLine();
            String[] parts = line.trim().split("\\s+");
            int K = Integer.parseInt(parts[0]); // 창문의 총 개수이다.
            int N = Integer.parseInt(parts[1]); // 돌을 던지는 악당의 수이다.
            int M = Integer.parseInt(parts[2]); // 강화하는 일꾼의 수이다.
            int H = Integer.parseInt(parts[3]); // 처음부터 강화된 창문의 개수이다.
            
            // 그룹 A는 강화된 창문, 그룹 B는 기본 창문이다.
            int countA = H;
            int countB = K - H;
            
            // 그룹 A에 대한 DP 테이블을 구성한다.
            // dpA[r][s]는 그룹 A의 창문에 대해 총 r회의 추가 강화와 s회의 돌 던지기가 이루어졌을 때의 기여도 합이다.
            // 그룹 A의 안전 조건은 ds ≤ r + 1이다.
            double[][] dpA = new double[M + 1][N + 1];
            dpA[0][0] = 1.0;
            for (int i = 0; i < countA; i++) {
                double[][] newdp = new double[M + 1][N + 1];
                // 현재까지의 강화 횟수(r0)와 돌 던진 횟수(s0)에 대하여 순회한다.
                for (int r0 = 0; r0 <= M; r0++) {
                    for (int s0 = 0; s0 <= N; s0++) {
                        double cur = dpA[r0][s0];
                        if (cur == 0.0) continue;
                        int remR = M - r0; // 남은 강화 횟수이다.
                        int remS = N - s0; // 남은 돌 던지기 횟수이다.
                        // 새 창문에 대해 가능한 (dr, ds) 조합을 시도한다.
                        // 단, 안전 조건은 ds ≤ dr + 1이다.
                        for (int dr = 0; dr <= remR; dr++) {
                            int maxDs = Math.min(remS, dr + 1);
                            for (int ds = 0; ds <= maxDs; ds++) {
                                // 한 창문에서의 기여도는 1/(dr! × ds!)이다.
                                double add = invFact[dr] * invFact[ds];
                                newdp[r0 + dr][s0 + ds] += cur * add;
                            }
                        }
                    }
                }
                dpA = newdp;
            }
            
            // 그룹 B에 대한 DP 테이블을 구성한다.
            // dpB[r][s]는 그룹 B의 창문에 대해 총 r회의 추가 강화와 s회의 돌 던지기가 이루어졌을 때의 기여도 합이다.
            // 그룹 B의 안전 조건은 ds ≤ r이다.
            double[][] dpB = new double[M + 1][N + 1];
            dpB[0][0] = 1.0;
            for (int i = 0; i < countB; i++) {
                double[][] newdp = new double[M + 1][N + 1];
                for (int r0 = 0; r0 <= M; r0++) {
                    for (int s0 = 0; s0 <= N; s0++) {
                        double cur = dpB[r0][s0];
                        if (cur == 0.0) continue;
                        int remR = M - r0;
                        int remS = N - s0;
                        // 그룹 B의 경우, 가능한 (dr, ds) 조합은 ds ≤ dr를 만족한다.
                        for (int dr = 0; dr <= remR; dr++) {
                            int maxDs = Math.min(remS, dr);
                            for (int ds = 0; ds <= maxDs; ds++) {
                                double add = invFact[dr] * invFact[ds];
                                newdp[r0 + dr][s0 + ds] += cur * add;
                            }
                        }
                    }
                }
                dpB = newdp;
            }
            
            // 두 그룹의 DP 결과를 합성하여 전체 generating function에서 x^M · y^N 항의 계수 S_total을 구한다.
            double S_total = 0.0;
            for (int rA = 0; rA <= M; rA++) {
                for (int sA = 0; sA <= N; sA++) {
                    int rB = M - rA;
                    int sB = N - sA;
                    if (rB < 0 || sB < 0) continue;
                    S_total += dpA[rA][sA] * dpB[rB][sB];
                }
            }
            
            // 전체 방이 안전한 상태(즉, 한 개의 창문도 깨지지 않은 상태)가 될 확률 P_safe는 아래와 같이 계산된다.
            // P_safe = (M! × N! / K^(M+N)) × S_total
            // 큰 수의 계산을 위하여 로그를 사용하여 계산한다.
            double logP_safe;
            if (S_total == 0.0) {
                logP_safe = Double.NEGATIVE_INFINITY;
            } else {
                logP_safe = logFact[M] + logFact[N] + Math.log(S_total) - (M + N) * Math.log(K);
            }
            double P_safe = (logP_safe == Double.NEGATIVE_INFINITY ? 0.0 : Math.exp(logP_safe));
            double ans = 1.0 - P_safe;
            if (ans < 0) ans = 0.0;
            if (ans > 1) ans = 1.0;
            
            out.printf("Case #%d: %.8f%n", t, ans);
        }
        out.flush();
        out.close();
    }
}

---

⏱️ 시간 복잡도 분석

본 알고리즘은 각 창문마다 가능한 강화와 돌 던지기 조합을 2차원 동적 계획법(DP)을 사용하여 계산한다. DP 배열의 크기는 (M+1)×(N+1)이며, 내부 반복문에서는 강화 횟수와 돌 던지기 횟수를 모두 고려한다.

그룹 A와 그룹 B의 창문 수의 합은 K(최대 200)개이므로, 전체 시간 복잡도는 제한 내에서 충분히 계산 가능하다.

---

💡 느낀점

본 문제는 단순해 보이는 상황을 수학적 모델링과 동적 계획법을 통하여 효과적으로 해결한 모범적인 사례이다. 각 창문의 내구성을 강화와 돌 던지기의 조합으로 세분화하여 안전 조건을 엄밀하게 정의한 점이 인상적이다. 또한, 큰 수의 연산에서 로그를 사용하여 오버플로우를 방지한 접근법은 계산의 안정성을 보장한다. 이러한 방법론은 복잡한 조합론 문제를 효율적으로 해결하는 데 큰 도움이 된다.