public class Main{
public static void main(String[] args){
}
}
문제 설명
접근 방법
이 문제에 핵심
1. 주사위의 면이 나올 확률이 동일하다고 가정합니다.
2. 주사위를 던졌을 때 기대값은 (주사위 숫자 합 / 면의 개수) 입니다.
3. 주사위 M개를 모두 던졌을 때 기대값의 합을 결과로 출력합니다.
알고리즘 진행 순서.
1. 입력된 정보를 저장합니다.
2. M개의 주사위를 던진 기댓값의 합을 구합니다.
3. 기댓갑의 합이 기약분수일 때와 아닐 때에 따른 결과를 출력합니다.
문제 내용 해석!
해석
N개의 면을 가진 주사위에 대해서 각 면이 나올 확률이 모두 동일할 때
기댓값 : (각 면 수의 합 / N)
해석
M개의 주사위를 던졌을 때 기댓값의 합
기댓값의 합 : 주사위1 기댓값 + 주사위2 기댓값 + ..... + 주사위M 기댓값
해석
기댓값의 합이 기약분수일 때 분모(역원)에 대한 값을 구하는 방법
역원의 값 : 페르마 소정리 이용!
페르마 소정리
조건 : n은 소수, a와 n은 서로수
해석
역원을 계산할 때 n은 1,000,000,007의 큰 소수를 이용하는 것이 가장 정확한 방식!
나머지를 계산할 때에는 모듈러 연산을 이용해라!
모듈러 연산
(a + b) mod n = (a mod n + b mod n) mod n
(a - b) mod n = (a mod n - b mod n) mod n
(a * b) mod n = (a mod n * b mod n) mod n
...
전체적인 해석!
각 주사위 기댓값 존재 ▶ 기댓값 합 구하기
▶ 기댓값 합이 기약 분수가 아닐 때 : 해당 값 결과로 출력!
▶ 기댓값 합이 기약 분수일때 ▶ 분자 × 분모의 역원(페르마 소정리) mod 1,000,000,007
▶ 나머지를 구할 때 모듈러 이용
예제입력 1.
1. 입력된 정보를 저장합니다.
M : 1
N₁ : 3
S₁ : 7
2. M개의 주사위를 던진 기댓값의 합을 구합니다.
1번 주사위
기댓값 : 7 / 3
M개의 주사위 기댓값 합 : 7 / 3
3. 기댓갑의 합이 기약분수일 때와 아닐 때에 따른 결과를 출력합니다.
7 / 3은 기약 분수!
분자 × 분모의 역원(페르마 소정리) mod 1,000,000,007
계산 : 333333338
333333338 결과로 출력합니다.
BufferedReader를 사용하여 입력되는 정보를 저장합니다.
StringTokenizer를 이용하여 각 주사위의 S와 N을 띄어쓰기 기준 나누었습니다.
M개 주사위 기댓갑 합을 구합니다.(기댓갑 합을 구할 때는 분모를 통분하는 방식을 채택)
기댓값이 기약분수이면 역원을 이용하여 계산한 값, 아닐 때는 해당 값을 결과로BufferedWriter에 저장하였습니다.
BufferedWriter에 저장된 결과값을 출력하였습니다.
search함수는 페르마 소정리의 공식과 모듈러 산술 규칙을 이용하여 역원을 계산합니다.
결과코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
static final int P = 1000000007; //나머지 기준 값
public static void main(String[] args) throws IOException{
//입력값 처리하는 BufferedReader
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//결과값 출력하는 BufferedWriter
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int M = Integer.parseInt(br.readLine());
StringTokenizer st;
long N = 1, S = 0;
//기댓값 합 구하기!
for(int i=0;i<M;i++) {
st = new StringTokenizer(br.readLine()," ");
int n = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken());
//각 분모와 분자를 통분하여 계산
S = s * N + S * n;
N *= n;
//모듈러 산술로 인하여 나머지 계산
S %= P;
N %= P;
}
//기약 분수일 때
if(S % N != 0)
bw.write((search(N, P-2) * S) % P + "");
else //기약 분수가 아닐 때
bw.write(S/N + "");
bw.flush(); //결과 출력
bw.close();
br.close();
}
//페르마 소정리, 모듈러 산술을 이용한 역원의 값 구하기!
static long search(long N, int index) {
if(index == 1)
return N;
long temp = search(N, index/2);
if(index % 2 == 1)
return temp * temp % P * N % P;
else
return temp * temp % P;
}
}
댓글