[BOJ/Java] 5266. Strange Dream

📌 [BOJ/Java] 5266. Strange Dream

🔗 문제 링크: 문제 보기

---

📖 문제 해석

Dumitru가 이상한 꿈을 꿨다. 꿈속에서 문이 잠긴 방에 갇힌 Dumitru는 n개의 박스를 발견했다. 각 박스에는 m개의 접시가 있었고, 각 접시에는 1 이상의 정수가 적혀 있었다. 그러던 중 두 개의 정수 k와 l이 적힌 쪽지를 발견했다. 쪽지에는 다음과 같은 작업을 하라고 되어 있었다.

 

1단계: 첫 번째 박스부터 n번째 박스까지 순서대로 각 박스에서 한 개의 접시를 선택한다. 선택한 접시의 숫자를 노트에 기록한 후, 해당 접시의 숫자를 1로 바꾼다.

2단계: n-1번째 박스부터 두 번째 박스까지 역순으로 각 박스에서 한 개의 접시를 선택한다.

목표는 노트에 기록된 숫자들의 곱이 k로 나누어 떨어지도록 하는 선택 방법의 총 가짓수 T를 구하고, T를 l로 나눈 나머지를 출력하는 것이다.

 

✅ 핵심 개념

• 정수론과 gcd를 활용해 k의 약수를 처리한다.
• 각 박스별 접시 선택의 경우의 수를 구분해 계산한다.
• 동적 계획법(DP)을 통해 상태 전이를 누적한다.

---

🛠️ 풀이 과정

먼저 입력으로 n, m, k, l과 각 박스의 접시에 적힌 수를 받았다. k의 모든 약수를 구해 각 약수를 상태로 사용하고, 약수에 대한 인덱스를 매핑했다.

 

각 박스마다 접시 선택의 경우의 수를 계산했다. 첫 번째 박스와 마지막 박스는 접시를 한 번만 선택하므로 각 접시가 기여하는 값이 그대로 반영되었다.

 

중간 박스는 두 번 선택하는 경우가 있어, 같은 접시를 두 번 선택하는 경우(두 번째 선택 시 1이 기록됨)와 서로 다른 접시를 선택하는 경우를 모두 고려했다.

 

DP 배열을 이용해 각 박스에서 계산된 경우의 수를 누적하며 상태 전이를 진행했다. 현재 상태는 지금까지 선택한 접시들의 숫자 곱의 gcd(k, ·) 값으로 표현된다.

 

모든 박스를 처리한 후, 최종 상태가 k로 나누어 떨어지는 경우의 수를 l로 나눈 나머지를 출력했다.

---

💻 코드 구현 (Java)

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

public class Main {
    public static void main(String[] args) throws Exception {
        // 입력을 위한 BufferedReader 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 첫 번째 줄: n (박스 개수), m (각 박스 당 접시 개수) 입력
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        // 두 번째 줄: k (목표 배수), mod (나머지 연산 모듈) 입력
        st = new StringTokenizer(br.readLine());
        int k = Integer.parseInt(st.nextToken());
        int mod = Integer.parseInt(st.nextToken());
        
        // k의 모든 약수를 구함 (각 상태를 약수로 사용)
        ArrayList<Integer> dlist = new ArrayList<>();
        for (int i = 1; i * i <= k; i++) {
            if (k % i == 0) {
                dlist.add(i);
                if (i * i != k)
                    dlist.add(k / i);
            }
        }
        // 약수를 오름차순으로 정렬
        Collections.sort(dlist);
        int dCount = dlist.size();
        int[] dArr = new int[dCount];
        for (int i = 0; i < dCount; i++) {
            dArr[i] = dlist.get(i);
        }
        
        // 각 약수에 인덱스를 매핑 (상태 전이 테이블 구성에 사용)
        HashMap<Integer, Integer> dIndex = new HashMap<>();
        for (int i = 0; i < dCount; i++) {
            dIndex.put(dArr[i], i);
        }
        
        // 두 상태의 곱셈 결과의 gcd(k, 곱)으로 전이되는 상태를 미리 계산 (상태 전이 테이블)
        int[][] mult = new int[dCount][dCount];
        for (int i = 0; i < dCount; i++) {
            for (int j = 0; j < dCount; j++) {
                long prod = (long) dArr[i] * dArr[j];
                int g = (int) gcd(prod, k);
                mult[i][j] = dIndex.get(g);
            }
        }
        
        // dp 배열 초기화 (현재 상태별 경우의 수 저장)
        int[] dp = new int[dCount];
        // 초기 상태는 1 (곱의 결과가 1)인 상태에서 시작
        dp[dIndex.get(1)] = 1;
        
        // 각 박스별로 처리 (총 n개의 박스)
        for (int box = 1; box <= n; box++) {
            // 각 박스 내에서 약수 상태에 해당하는 접시 개수 카운트
            int[] freq = new int[dCount];
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                int val = Integer.parseInt(st.nextToken());
                int g = (int) gcd(val, k);
                int idx = dIndex.get(g);
                freq[idx]++; // 해당 약수 상태에 해당하는 접시 개수 증가
            }
            
            // 현재 박스에서 선택할 경우의 수를 계산할 배열
            int[] boxDist = new int[dCount];
            if (box == 1 || box == n) {
                // 첫 번째 박스와 마지막 박스는 한 번만 선택하므로 그대로 사용
                for (int i = 0; i < dCount; i++) {
                    boxDist[i] = freq[i] % mod;
                }
            } else {
                // 중간 박스는 두 번 선택함 (한 번은 기록 후 1로 변경, 두 번 선택 시 곱에 영향 없음)
                int[] doubleDist = new int[dCount];
                // 먼저 한 번 선택하는 경우 (기본적으로 freq 값을 더함)
                for (int i = 0; i < dCount; i++) {
                    doubleDist[i] = (doubleDist[i] + freq[i]) % mod;
                }
                // 두 번째 선택의 경우: 같은 접시 또는 다른 접시 선택 경우 고려
                for (int i = 0; i < dCount; i++) {
                    for (int j = 0; j < dCount; j++) {
                        // i와 j가 같은 경우: 같은 접시를 두 번 선택하는 경우
                        // i와 j가 다른 경우: 서로 다른 접시를 선택하는 경우
                        long ways = (i == j) ? (long) freq[i] * (freq[i] - 1) : (long) freq[i] * freq[j];
                        if (ways == 0)
                            continue;
                        int idx = mult[i][j];
                        doubleDist[idx] = (int) ((doubleDist[idx] + ways) % mod);
                    }
                }
                boxDist = doubleDist;
            }
            
            // 현재까지의 dp와 이번 박스의 boxDist를 이용해 다음 상태(ndp)를 계산
            int[] ndp = new int[dCount];
            for (int i = 0; i < dCount; i++) {
                if (dp[i] == 0)
                    continue;
                for (int j = 0; j < dCount; j++) {
                    if (boxDist[j] == 0)
                        continue;
                    int ns = mult[i][j]; // 현재 상태 i에서 박스의 선택 j를 적용한 새로운 상태
                    ndp[ns] = (int) ((ndp[ns] + (long) dp[i] * boxDist[j]) % mod);
                }
            }
            // dp 배열 갱신
            dp = ndp;
        }
        // 최종적으로 dp 배열에서 목표 상태 k (즉, 약수 상태가 k가 되는 경우)의 값을 출력
        System.out.println(dp[dIndex.get(k)] % mod);
    }
    
    // 유클리드 호제법을 이용한 최대공약수(GCD) 계산 메소드
    static long gcd(long a, long b) {
        while (b != 0) {
            long t = a % b;
            a = b;
            b = t;
        }
        return a;
    }
}

---

⏱️ 시간 복잡도 분석

문제는 각 박스마다 m개의 접시를 처리하고, k의 약수 개수를 d라 할 때 O(n*m + n*d²)의 시간 복잡도를 가진다.
n은 최대 200, m은 최대 10,000이며, d는 k의 약수 개수로 보통 √k에 가까워 제한 내에서 충분히 계산된다.

---

💡 느낀점

문제 접근 방식은 각 박스에서의 접시 선택에 따른 상태 전이를 명확하게 처리하는 데 초점을 두었다.
정수론과 gcd를 활용해 k의 약수를 처리하며 상태 전이 테이블을 구성한 점이 인상적이다.
동일한 박스에서 접시를 두 번 선택하는 경우를 세밀하게 고려한 점이 문제 해결의 핵심 포인트였다.