[11051] 이항 계수 2

✔ 이항 계수 2

[백준 11051]

문제 분석하기

조합의 일반 점화식에서 결괏값이 나올 때마다 10007으로 모듈러 연산을 수행하는 로직을 추가

손으로 풀어보기

1. N과 K의 값을 입력받고 DP 배열을 선언
   • D[N + 1][N + 1]
2. DP 배열의 값을 초기화
   • i개 중 1개를 뽑는 경우의 수인 D[i][1] = i
   • i개 중 0개를 뽑는 경우의 수인 D[i][0] = 1
   • i개 중 i개를 뽑는 경우의 수인 D[i][i] = 1
3.  점화식으로 DP 배열의 값을 채움
   • D[i][j] = D[i - 1][j] + D[i - 1][j - 1]
   • 이때 점화식의 결괏값이 나올 때마다 MOD 연산을 수행
4. D[N][K]의 값을 출력함

슈도코드 작성하기

N(총 개수), K(선택 수)
D(DP 배열)
for(i -> N만큼 반복하기) {
    D 배열 초기화하기
    D[i][1] = i
    D[i][0] = 1
    D[i][i] = 1
}
for(i -> N만큼 반복하기) {
    for(j -> i만큼 반복하기) {
        D[i][j] = D[i - 1][j] + D[i - 1][j - 1]
        D[i][j] 값을 10007로 mod 연산한 값으로 업데이트하기
    }
}
D[N][K]

코드 구현하기

/**
 * 11051) 이항_계수_2
 */
public class D077_11051 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // N(총 개수)
        int N = sc.nextInt();
        // K(선택 수)
        int K = sc.nextInt();
        // D(DP 배열)
        int[][] D = new int[N + 1][N + 1];
        // D 배열 초기화하기
        for (int i = 0; i <= N; i++) {
            D[i][1] = i;
            D[i][0] = 1;
            D[i][i] = 1;
        }
        for (int i = 2; i <= N; i++) {
            // 고르는 수의 개수가 전체 개수를 넘을 수 없음
            for (int j = 1; j < i; j++) {
                // 조합 점화식
                D[i][j] = D[i - 1][j] + D[i - 1][j - 1];
                // D[i][j] 값을 10007로 mod 연산한 값으로 업데이트하기
                D[i][j] = D[i][j] % 10007;
            }
        }
        System.out.println(D[N][K]);
    }
}