BOJ_13172 : Σ

👉 문제링크

13172번: Σ

---

---

🔸 문제 분석 🔸

• 주사위 M개에 대해 i번째 주사위의 면 개수는 Ni, 면의 모든 값의 총합은 Si로 입력된다.
• 모든 주사위를 던졌을 때의 기대값을 계산한다.
  • S1/N1 + S2/N2 + ... + SM/NM  계산의 어려움 때문에 임의의 분수 a / b를 모듈러를 이용해 (a * b-1 mod x)의 정수 값으로 계산한다.

🔸 문제 풀이 🔸

• 문제의 수학 이론 설명이 꽤 길지만, 읽어보면 이해 못할 정도는 아니다. 보다 정확한 확률 계산을 위해 모듈러 표현 방식을 사용한다는 것이다.
• 문제에서 제시된 공식을 사용하면 되는데, 중요한건 a/b를 a * b^-1 mod X로 변환해 누적하는 것이다.
  • b^-1 (mod X)은 페르마의 소정리에 의해 b^(X-2) (mod X)와 같다고 한다.
  • 모듈러 값이 1,000,000,007이므로,  S * N^(1,000,000,007 - 2) % 1,000,000,007 값을 누적 후 출력한다.
• 거듭제곱의 값이 모듈러 값-2 로 아주 크므로 빠른 거듭제곱 알고리즘 (Fast Power Algorithm)을 사용한다.

  

  빠른 거듭제곱 알고리즘 점화식 (출처:이미지클릭)

🔸 코드 🔸

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

public class Main {
    private static final int MOD = 1_000_000_007;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int M = Integer.parseInt(br.readLine());

        long answer = 0;

        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken()); // 주사위 면 개수
            int S = Integer.parseInt(st.nextToken()); // 주사위 면 총합

            long b = S * fast_power_algorithme(N, MOD - 2) % MOD;
            answer = (answer + b) % MOD;
        }

        bw.write(Long.toString(answer));
        bw.flush();
    }

    private static long fast_power_algorithme(long a, int n) {
        long r = 1;
        while (n > 0) {
            if ((n & 1) == 1) r = r * a % MOD;
            a = a * a % MOD;
            n >>= 1;
        }
        return r;
    }
}

🔸 코드 해석 🔸

• 주사위 면의 개수 N과 주사위 값의 총합 S를 입력받아 기대값을 계산해 누적한다.
  • 기대값은 S/N으로 계산하는데, 문제에서 제시된 모듈러 공식에 따라 S * (N의 mod-1 제곱) %mod로 계산한다.
• 거듭제곱의 수가 크므로 빠른 거듭제곱 알고리즘을 사용하기 위해 fast_power_algorithm() 메서드를 구현했다.
  • 비트 단위로 확인해 값을 거듭제곱한다. 이때 값을 mod로 모듈러 연산을 해서 값이 커지지 않도록 한다.
• 값을 누적할 때도 모듈러 연산을 반복한다.
• 누적 값을 출력한다.

---

🔸 end 🔸

• 초반에 문제 이해는 어느정도 했지만, 주어진 공식을 코드로 어떻게 옮겨야 한다는 건지 감을 잡지 못해 풀이를 참고했다.
  • 해당 문제의 C++풀이 질문글을 참고했는데, 바로 이해가 되어서 풀이할 수 있었다.
  • 질문글에 거듭제곱을 특이하게 구현했길래 찾아보았는데 빠른 거듭제곱 알고리즘을 사용했다는 걸 알 수 있었다.
• Math.pow로 계산했을때는 주어진 모듈값을 계산하지 못하고 Infinity가 났었다.
  • 빠른 거듭제곱 알고리즘 설명 포스팅을 참고해 원리를 이해하고 적용했다.
  • 구현하고 보니 질문글에 구현되어 있던 형태가 그대로 적용되어서 조금 허무했지만 좋은 공부가 되었다.
• 풀고나서 알고리즘 분류를 보니, 분할 정복을 이용한 거듭제곱, 모듈로 곱셈 역원, 페르마의 소정리 태그를 처음 본 것 같았다.
  • 모듈로 곱셈 역원과 페르마의 소정리는 문제에 제시된 수학 원리를 사용한 문제들인 것 같다.
  • 분할정복을 이용한 거듭제곱은 위에서 나온 빠른 거듭제곱 알고리즘이 분할정복에서 아이디어가 나와서 그런 것 같다.