Baekjoon11401: 이항 계수3

Baekjoon11401: 이항 계수3

풀이1 이항계수의 다항식성질

이항계수의 다항식의 성질을 생각할 수 있지만 반복문을 사용하기 때문에 시간초과가 발생한다.

4백만 크기의 n을 입력하면 시간초과는 뻔하기 때문에 백준에 입력하지는 않았다.

현재 배열의 값들을 오른쪽으로 한칸씩 옮기는데 오른쪽 끝부터 오른쪽으로 한 칸씩 옮긴다.

옮기면서 원래 그 자리에 있던 수와 더한다.

이를 마치면 (n k) 줄에 해당하는 식이 완성되어있고 이 배열의 k번째 index의 값을 출력하면 된다.

import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] arr = new int[N+1]; arr[0]=1; for(int i=0;i=0;j--) { arr[j+1]=(arr[j+1]+arr[j])%1000000007; } } System.out.println(arr[sc.nextInt()]); }}

풀이2 배열을 이용한 분할정복

결국 2배씩 앞당겨서 찾는 방법을 생각해야했는데, 위 다항식을 분할정복을 통해 구현할 수 있다.

예를 들면 0번째줄부터 4번째 줄을 나타내면 다음과 같이 (x+1)^n의 다항식 계수로 표현할 수 있을 것이다.

1 = (x+1)의 0승

1 1 = x+1

1 2 1 = x^2 + 2x + 1 = (x+1)^2

1 3 3 1 = (x+1)^3

이를 통해 (n k)의 결과값은 (x+1)^n의 k번째 항의 계수임을 알 수 있고

규칙성을 이용해 n을 절반으로 쪼개가며 다항식의 곱으로 표현할 수 있다.

(x+1)^n = (x+1)^n/2 * (x+1)^n/2

메소드

(x^2+2x+1) (x+1)의 결과를 어떻게 표현할 수 있을까?

배열로 나타내면 {1, 2, 1, 0}, {1, 1, 0, 0} 이다.

{1, 2, 1, 0}, {1, 1, 0, 0}: 각 index는 x가 몇번 곱해져있는지 알려준다. 오른쪽부터 계산하면 → {0, 0, 0, 1}

{1, 2, 1, 0}, {1, 1, 0, 0}: index[0]을 곱하면 자리는 변하지 않는다 → {0, 0, 1, 1}

{1, 2, 1, 0}, {1, 1, 0, 0}: index[1]을 곱하면 자리는 +1만큼 변한다 → {0, 0, 3, 1}

{1, 2, 1, 0}, {1, 1, 0, 0}: index[0]을 곱하면 자리는 변하지 않는다 → {0, 2, 3, 1}

다항식의 연산과 분할정복을 합해봤지만 시간초과였다

import java.util.*; public class Main { static int N; static long[] arr; static long[] pascal(int N) { if(N==0 || N==1) { return arr; } long[] before = pascal(N/2); long[] answer = cal(before,N/2+1,before,N/2+1); if(N%2==0) { return answer; }else { return cal(answer,N-1,arr,2); } } static long[] cal(long[] A, int lenA,long[] B, int lenB) { long[] C = new long[N+1]; for(int i=0;i

풀이 3 페르마 소정리를 이용한 분할정복

성질을 이용해서 4000000 사백만의 n에 도달하는 것은 어렵다고 결론지었다.

결국 자체식인 (n k) = n!/k!(n-k)! 을 사용해야했다.

나눗셈이 들어간 식에서 모듈러 연산을 사용할 수 없기 때문에 모듈러 연산을 사용하기 위해 등식을 이용해 식을 변경한다.

(n k) = B/A = B*A^-1 = n!/k!(n-k)! → A = k!(n-k)! → A^-1 = 1 / k!(n-k)! 의 식으로 나타낼 수 있고 페르마의 소정리를 적용한다.

<페르마의 소정리: p가 모듈러>

A^(p-1) ≡ 1

A^(p-2) ≡ A^-1

이에 위의 식은 (n k) = B/A = n!/k!(n-k)! → n! * {k!(n-k!)}^(1000000007-2) 가 된다.

메소드1

각각의 팩토리얼을 계산하는 메소드를 만든다.

예시) n! → n번 곱하면서 모듈러 연산진행

메소드2

분할정복으로 지수승을 구하는 메소드를 만든다.

import java.util.*; public class Main { static long MOD = 1000000007; static long Factorial(int n) { long sum=1; for(int i=1; i<=n; i++) { sum=(sum*i)%MOD; } return sum; } static long power(long a, long b) { if(b==1) { return a; } long before = power(a,b/2)%MOD; long now = before*before%MOD; if(b%2==0) { return now; }else { return now*a%MOD; } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int K = sc.nextInt(); long A = Factorial(N),B = Factorial(K),C = Factorial(N-K); long D = B*C%MOD; System.out.println(A*power(D,MOD-2)%MOD); }}

from http://devyoseph.tistory.com/199 by ccl(A) rewrite - 2021-12-29 11:27:39