★백준/11051 이항 계수 2 /조합,BigInteger,파스칼의 삼각형

이항 계수 2 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

48877

18134

14257

37.642%

문제

자연수 N\(N\)과 정수 K\(K\)가 주어졌을 때 이항 계수 (NK)\(\binom{N}{K}\)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

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

출력

 (NK)\(\binom{N}{K}\)를 10,007로 나눈 나머지를 출력한다.

예제 입력 1 복사

5 2

예제 출력 1 복사

10

---

풀이

이항계수1 도 조합으로 풀어서 조합으로 하려니까 조합의 시간복잡도는 O(2^n)이라서 시간초과에 걸릴것 같았다.

그래서 

위와 같은 조합공식을 이용하기로하였고

각 팩토리얼을 구하는법은 시간초과가 뜨지않게 메모이제이션을 이용하려고 했다.

그러나 시간초과로 실패 -> 잘못짠듯하다 , 그렇게 짰어도 최대 갯수인 1000! 에 대한값은 int이든 long이든 넘어갈것이 뻔했다.

 

BigInteger 사용

빅인티저는 수를 스트링으로 받아 연산해줘서 수의 범위가 상관없다고 한다.

import java.io.*;
import java.math.BigInteger;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


   static int n;
   static int k;
    static int[] factoArray;

    public static void main(String[] args) throws IOException {
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        k = Integer.parseInt(input[1]);

        BigInteger nFac = facto(BigInteger.valueOf(n));
        BigInteger rFac = facto(BigInteger.valueOf(k));
        BigInteger nMinusRfac = facto(BigInteger.valueOf(n-k));

        BigInteger result = nFac.divide(nMinusRfac.multiply(rFac))
            .remainder(new BigInteger("10007"));

        bw.write(result.toString());

        bw.flush();
        bw.close();

    }

    public static BigInteger facto(BigInteger n) { //메모이제이션을 이용한 팩토리얼 구하기
        BigInteger result = new BigInteger("1");
        for (int i = 1; i <= n.intValue(); i++) {
            result = result.multiply(BigInteger.valueOf(i));
        }
        return result;

    }

}

 

다른사람 풀이

동적프로그래밍 + 파스칼의 삼각형 이용

5C2 -> 4C1 + 4C2 이고 4C2는 다시 3C1 + 3C2 가 되는 것을 이용

nCn -> 1 

nC0 -> 1  을 사용해서

조합의 값을 구한다.

 

동적프로그래밍 + 파스칼의 삼각형 이용해서 다시 푼 코드

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


   static int n;
   static int k;
   static int[][] paskalTri;

    public static void main(String[] args) throws IOException {
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        k = Integer.parseInt(input[1]);
        paskalTri = new int[n+1][n+1];  // nCr에서 n과 r의 범위가 1~n이여야하니까 n+1로 크기를 잡는다.

        combi(n, k);
        bw.write(paskalTri[n][k] + "");


        bw.flush();
        bw.close();

    }

    public static void combi(int n, int r) { //메모이제이션 , 파스칼삼각형을 내가 원하는값까지 채워준다.
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= r; j++) {
                if (i == j || j == 0) {
                    paskalTri[i][j] = 1;
                }
                else{
                    paskalTri[i][j] = (paskalTri[i - 1][j] + paskalTri[i - 1][j - 1])%10007;
                }

            }
        }
    }

}