[BOJ/Java] 6902. Orko

📌 [BOJ/Java] 6902. Orko

🔗 문제 링크: 문제 보기

---

📖 문제 해석

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

 

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

 

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

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

---

🛠️ 풀이 과정

먼저, n, m, k, l과 각 박스의 접시 값들을 입력받는다. 문제의 핵심은 k의 약수를 상태로 활용하는 것이다. k의 모든 약수를 구한 뒤, 각 약수에 인덱스를 매핑하여 상태 전이 테이블을 구성한다.

 

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

 

중간 박스는 접시를 두 번 선택하는 경우가 있으므로, 첫 번째 선택(접시의 원래 숫자 기록)과 두 번째 선택(접시 숫자가 1로 변경됨)을 모두 고려하여 경우의 수를 누적한다.

 

동적 계획법(DP)을 이용해 각 박스에서 계산된 경우의 수를 누적하며, 현재까지 선택한 접시들의 곱의 gcd(k, ·) 값을 상태로 표현하여 전이를 수행한다.

 

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

---

💻 코드 구현 (Java)

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

public class Main {

// 유클리드 호제법을 이용하여 최대공약수(GCD)를 구하는 메소드
static long gcd(long a, long b) {
    // b가 0이 될 때까지 반복
    while (b != 0) {
        long temp = a % b;  // a를 b로 나눈 나머지를 임시 저장
        a = b;              // a에 b 값을 대입
        b = temp;           // b에 나머지 값을 대입
    }
    return a;             // 최대공약수 반환
}

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 product = (long) dArr[i] * dArr[j];
            int g = (int) gcd(product, k);
            mult[i][j] = dIndex.get(g);
        }
    }
    
    // DP 배열 초기화: dp[i]는 현재 상태가 dArr[i]일 때의 경우의 수
    int[] dp = new int[dCount];
    // 초기 상태는 접시 선택 전 곱이 1인 상태
    dp[dIndex.get(1)] = 1;
    
    // 각 박스를 순서대로 처리
    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 plateValue = Integer.parseInt(st.nextToken());
            int g = (int) gcd(plateValue, k);
            int idx = dIndex.get(g);
            freq[idx]++;  // 해당 상태의 빈도수 증가
        }
        
        // 현재 박스에서 선택 가능한 경우의 수 분포를 저장할 배열
        int[] boxDist = new int[dCount];
        
        // 첫 번째 박스와 마지막 박스는 접시를 한 번만 선택하므로 단순히 freq 값을 사용
        if (box == 1 || box == n) {
            for (int i = 0; i < dCount; i++) {
                boxDist[i] = freq[i] % mod;
            }
        } else {
            // 중간 박스는 접시를 두 번 선택해야 함
            // 첫 번째 선택: 접시의 원래 숫자를 기록
            // 두 번째 선택: 해당 접시의 숫자가 1로 변함
            int[] doubleDist = new int[dCount];
            
            // 첫 번째 선택의 경우의 수를 추가
            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++) {
                    long ways;
                    if (i == j) {
                        // 같은 접시를 두 번 선택하는 경우
                        ways = (long) freq[i] * (freq[i] - 1);
                    } else {
                        // 서로 다른 접시를 선택하는 경우
                        ways = (long) freq[i] * freq[j];
                    }
                    if (ways == 0)
                        continue;
                    
                    // 두 선택의 결과 상태를 상태 전이 테이블을 이용해 계산
                    int newIndex = mult[i][j];
                    doubleDist[newIndex] = (int) ((doubleDist[newIndex] + ways) % mod);
                }
            }
            boxDist = doubleDist;
        }
        
        // 현재까지의 dp 배열과 현재 박스의 경우의 수(boxDist)를 이용하여 상태 전이를 수행
        int[] nextDP = 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 nextState = mult[i][j];  // 상태 전이
                nextDP[nextState] = (int) ((nextDP[nextState] + (long) dp[i] * boxDist[j]) % mod);
            }
        }
        
        // dp 배열을 업데이트
        dp = nextDP;
    }
    
    // 최종적으로 목표 상태 k(즉, k로 나누어 떨어지는 상태)의 경우의 수를 mod로 나눈 나머지를 출력
    System.out.println(dp[dIndex.get(k)] % mod);
}

---

⏱️ 시간 복잡도 분석

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

---

💡 느낀점

문제 해결 과정에서 각 박스에서 접시 선택에 따른 상태 전이를 명확하게 처리하는 것이 핵심이었다.
정수론과 gcd를 활용하여 k의 약수를 상태로 처리한 점, 그리고 중간 박스에서 두 번 선택하는 경우를 세밀하게 고려한 점이 인상적이었다.