백준 11051 이항 계수 2[Java]

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

풀이

• 처음에는 아래의 식을 사용하여 재귀함수를 이용하여 풀었다.
  nCr = n-1Cr + n-1Cr-1
• 하지만 입력 범위가 1000까지 가기 때문에 메모이제이션을 사용하여 조합 수를 배열에 저장하여 풀었다.
• 하지만 다음 코드를 제출하면 틀렸습니다 가 뜬다.

import java.io.*;
import java.util.*;

public class Main {

    static int[][] cal = new int[1001][1001];

    public static int comb(int a, int b) {
        if (cal[a][b] != 0)
            return cal[a][b];

        if (b == 0 || a == b) {
            return cal[a][b] = 1;
        }

        return cal[a][b] = comb(a-1, b) + comb(a-1, b-1);
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        System.out.println(comb(a, b) % 10007);
    }
}

• 위의 코드가 틀린 이유는 입력 범위가 1 ≤ N ≤ 1000 이므로 너무 숫자가 커져 overflow가 발생하여 잘못된 값을 발생시키기 때문이다.
• 이를 해결하기 위해 모듈러 연산의 성질을 이용한다.
  

코드

import java.io.*;
import java.util.*;

public class Main {

    static int[][] cal = new int[1001][1001];

    public static int comb(int a, int b) {
        if (cal[a][b] != 0)
            return cal[a][b];

        if (b == 0 || a == b) {
            return cal[a][b] = 1;
        }

        return cal[a][b] = (comb(a-1, b)%10007 + comb(a-1, b-1)%10007)%10007;
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        System.out.println(comb(a, b));
    }
}

참고: https://st-lab.tistory.com/162