[백준] 이항 계수 3(11401)

문제

[백준] 이항 계수 3

자연수 N과 정수 K가 주어졌을 때 이항 계수 (N K)(자세한 문제는 위의 링크를 통해 확인해주세요)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 4,000,000, 0 ≤ K ≤ N)

출력

(N K)를 1,000,000,007로 나눈 나머지를 출력한다.

해설

이항 계수 점화식(nCk)을 적용했지만 결과는 메모리 초과였다. DP를 이용해 최적화 해주면 O(N^2)이라는 시간복잡도를 가지지만 N이 최대 4,000,000이기에 메모리도 많이 사용하고 시간도 오래걸려서 효율성이 떨어진다.

아래는 실패한 코드이다.

import java.util.*;

// 메모리초과
public class Main {
	static final int MOD = 1000000007;
	static long[][] dp;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int k = sc.nextInt();

		dp = new long[n + 1][n + 1];

		System.out.println(combination(n, k));
	}

	public static long combination(int n, int k) {
		if (n == 0 || n == 1 || k == 0 || n == k)
			return dp[n][k] = 1;

		if (dp[n][k] != 0)
			return dp[n][k];

		dp[n - 1][k - 1] = combination(n - 1, k - 1);
		dp[n - 1][k] = combination(n - 1, k);
		return dp[n][k] = dp[n - 1][k - 1] + dp[n - 1][k] % MOD;
	}
}

참고 자료
https://rh-tn.tistory.com/32
https://ko.vvikipedla.com/wiki/Binomial_coefficient

해당 문제는 모듈러 연산과 페르마의 소정리를 이용해 푸는 문제였다. 곱셈 문제의 응용버전이라 생각한다.

너무 어렵게 느껴진다면 아래 블로그를 참고해 페르마의 소정리를 익히고 풀이해보길 추천한다👍

참고 블로그
https://st-lab.tistory.com/241
https://m.blog.naver.com/hongjg3229/221650178981
https://kyunstudio.tistory.com/60

factorial 메서드에서 while문을 돌릴 때, res 계산을 res *= (n % P)로 구현하는 실수가 있었다. 예를 들어 (7 * 6 * 5) % P를 위의 식에 적용한다면 res = ((7 % P) * (6 % P) * (5 % P)) % P가 되기 때문에 return할 때 res % P를 해줘야 정확한 결과를 출력할 수 있다. 이때의 문제점은 (n % P) 값을 res에 계속 곱하다보면 지정된 범위를 넘는 수가 나올 수 있으므로 잘못된 구현이 된다.

즉, 올바른 구현은 res = (res * n) % P이다.

풀이

import java.util.*;

public class Main {
	static final long P = 1000000007;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		long N = sc.nextLong();
		long K = sc.nextLong();

		long A = factorial(N);
		long B = factorial(K) * factorial(N - K) % P;

		System.out.println(A * pow(B, P - 2) % P);
	}

	public static long factorial(long n) {
		long res = 1L;

		while (n > 1) {
			res = (res * n) % P;
			n--;
		}

		return res;
	}

	public static long pow(long B, long exponent) {
		if (exponent == 1)
			return B % P;

		long temp = pow(B, exponent / 2);

		if (exponent % 2 == 1)
			return (temp * temp % P) * B % P;

		return temp * temp % P;
	}
}