[Java] 백준 13172번 - Σ(시그마)

https://www.acmicpc.net/problem/13172

 

문제 요약

 

n면체 주사위에 적힌 숫자의 합이 s라면, 기댓값은 s/n이다.

m개의 주사위의 n값과 s값이 주어졌을때, 기댓값의 합을 구하면 된다.

 

단, 기댓값이 분수라면 정확한 답을 구하기가 힘들기 때문에 모듈러 곱셈에 대한 역원(b ^ -1)을 활용한다. 모듈러 곱셈에 대한 역원은 다음을 만족한다.

 

따라서 기댓값이 기약분수 a/b라면,  (a × b^-1) mod 1,000,000,007으로 대신한다.

 

 

 

 

 

 

단순한 풀이

 

이 문제의 풀이 과정은 간단하다. (다만 수학공식이 나와서 진입장벽이 높을 뿐이다!)

1) 주사위의 면수 n, 적힌 숫자의 합 s의 기댓값은 s/n이다.
2) s/n을 기약분수로 만든다. 
3) s/n 대신 (s * n^-1)  % MOD로 나타낸다. 

 

 

로직을 체크하기 위해, 우선적으로 수학 공식을 배제하고 코드를 짜봤다.

 

// 기약분수를 만드는 함수
private static long[] getRedycedFraction(int n, int s) {
	int end = Math.min(n, s);
	long a = s;
	long b = n;
		
	long operand = 2;
	while (operand <= end) {
		if (a % operand == 0 && b % operand == 0) {
			a /= operand;
			b /= operand;
		} else {
			operand++;
		}
	}
		
	return new long[] {a, b};
}

 

기약분수를 만드는 방법은 간단하다. 더이상 나누어지지 않을때까지 나누면 된다.

 

 

b의 모듈러 역원을 구하는 것은 어렵지만, 단순한 방법으로 접근해본다. 위의 식을 조금만 변형하면, (b * x) % MOD = 1이면 x가 b의 모듈러 곱셈의 역원이다. 모듈러 곱셈의 역원이 존재하지 않는 경우는 이 문제에서 존재하지 않는다.

 

// 모듈러 곱셈의 역원 구하기
private static int getReverseModuler(long n) {
	for (int i = 1; i < MOD; i++) {
		if ((i * n) % MOD == 1) {
			return i;
		}
	}
    
    // 모듈러 곱셈의 역원이 존재하지 않는 경우 (문제에서는 입력으로 주어지지 않음)
	return -1;
}

 

x를 1부터 MOD까지 하나씩 다 테스트해보면서, 1일 경우 리턴해준다. 당연히 !! 시간 초과가 난다. 하지만 테스트케이스를 통해 해당 로직에는 문제가 없다는 것을 알 수 있다. 따라서, 여기에다가 공식을 적용해서 시간을 줄인다.

 

 

 

 

 

 

 

모듈러 곱셈의 역원 - 페르마의 소정리 적용

 

 

문제에서 친절하게 모듈러 곱셈의 역원을 간단하게 구할 수 있는 페르마의 소정리를 제공해준다. b의 모듈러 곱셈의 역원은, b의 MOD -2승과 같다. (문제에서 X의 값이 10_0000_0007로 소수이기때문에 적용 가능하다.)

private static long getReverseModuler(int num) {
	return pow(num, MOD-2);
}

 

 

다만 MOD가 10억쯤되는 매우 큰 값이므로, 분할 정복을 통해 거듭제곱을 구해준다.

private static long pow(int num, int cnt) {
	if (cnt <= 1) {
		return num;
	}
		
	long temp = pow(num, cnt/2);
	return ((temp * temp) % MOD * (cnt%2==1 ? num : 1)) % MOD;
}

 

 

 

 

 

 

 

기약분수 구하기 - 유클리드 호제법 적용

 

* 유클리드 호제법에 대한 내용은 아래 사이트를 참고했다.

https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm

The Euclidean Algorithm (article) | Khan Academy

 

 

 

그다음은 기약분수를 구하는 과정을 단순화한다. s/n을 기약분수로 바꾸려면, 그들의 최대공약수(GCD)로 나누어주면 된다.

 

// 기약분수를 구하는 법 => 최대 공약수로 나눔
private static int[] getRedycedFraction(int s, int n) {
	int GCD = getGCD(s, n);
		
	return new int[] {s / GCD, n / GCD};
}

 

 

최대공약수를 구하기 위해서는 유클리드 호제법을 적용할 수 있다.

유클리드 호제법은 (A = B⋅Q + R)라면 GCD(A,B) = GCD(B,R)이라는 것이다.

 

우선, 유클리드 호제법을 적용하기 위해선 A != 0 && B != 0이라는 조건을 만족해야한다. 조건을 만족하지 못할 경우 A가 0이라면 B를, B가 0이라면 A를 리턴한다.

 

조건을 만족할 경우, GCD(A, B)를 A에 대한 식으로 바꿔본다. 

A가 270, B가 192일 경우 270 = 192 * 1 + 78로 나타낸다. 따라서, 유클리드 호제법에 의해 GCD(270, 192) == GCD(192, 78) 과 동일하다. 즉, GCD(A, B) = GCD(B, A%B)로 나타낼 수 있다.

 

이런식으로 계속해서 타고들면서, A나 B가 0이라서 특정 값을 리턴할때까지 재귀함수를 호출한다.

// 유클리드 호제법을 이용한 최대공약수 구하기
public static int getGCD(int a, int b) {
	if ( a== 0 || b == 0) {
		// x ^ 0 == x 이므로 a^b를 하면 0이 아닌 값을 리턴함
		return a^b; 
	}
		
	return getGCD(b, a%b);
}

 

 

 

 

 

전체 코드

 

문제 자체가 이해하기 어렵지만, 문제에서 주는 공식들을 잘 적용하면 생각보다 간단하게 해결할 수 있는 문제였다. 다만 유클리드 호제법은 주어지지 않으므로 숙지하고 있는 것이 필요하다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	final static int MOD = 10_0000_0007;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int m = Integer.parseInt(br.readLine());
		
		StringTokenizer st = null;
		long ans = 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());
			
			int[] num = getRedycedFraction(s, n);
			
			if(num[1] == 1) {
				ans += num[0] % MOD;
				ans %= MOD;
				continue;
			}
			
			long reverseModuler = getReverseModuler(num[1]);
			ans += (num[0] * reverseModuler) % MOD;
			ans %= MOD;
		}
		
		System.out.println(ans);
	}
	
	// 유클리드 호제법을 이용한 최대공약수 구하기
	public static int getGCD(int a, int b) {
		if ( a== 0 || b == 0) {
			// x ^ 0 == x
			return a^b; 
		}
		
		return getGCD(b, a%b);
	}
	
	// 기약분수를 구하는 법 => 최대 공약수로 나눔
	private static int[] getRedycedFraction(int s, int n) {
		int GCD = getGCD(s, n);
		
		return new int[] {s / GCD, n / GCD};
	}
	
	// 페르마 소정리 num ^ MOD-2 == num ^ -1
	private static long getReverseModuler(int num) {
		return pow(num, MOD-2);
	}

	private static long pow(int num, int cnt) {
		if (cnt <= 1) {
			return num;
		}
		
		long temp = pow(num, cnt/2);
		return ((temp * temp) % MOD * (cnt%2==1 ? num : 1)) % MOD;
	}
}