[백준/JAVA] 11051번: 이항 계수 2

🔺 문제

11051번: 이항 계수 2

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[][] D;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        
        // DP 배열 초기화
        D = new int[N + 1][N + 1];
        for(int i = 1 ; i <= N ; i++) {
            D[i][1] = i;
            D[i][0] = 1;
            D[i][i] = 1;
        }
        
        // DP 배열 채우기 (여기서 MOD 연산 수행)
        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;   // 모듈러 연산!
            }
        }
        
        System.out.println(D[N][K]);
        br.close();
    }
}

✅ 해결 아이디어
✔ 조합
→ DP
→ 점화식
→ 모듈러 연산! (26번째 줄)

 

💥 유의사항

•  이전 문제보다 N 범위가 커졌고, 결과값을 10007로 나눈 나머지를 출력해야 함

⇨ 모듈러 연산

(A mod N + B mod N)mod N = (A+B)mod 

 

---

🔺 다른 풀이들

- 모듈러 연산 설명까지.. 최고

[백준] 11051번 : 이항 계수 2 - JAVA [자바]

 

 

- 이렇게 푸신 분들이 더 많았다.

 

[백준] 11051번 : 이항 계수 2(JAVA)

---

💬 느낀 점

모듈러 연산을 잊지 말자!!

 

사실 조합 점화식도 잊은지 좀 되었다...하하하

r! - 순서가 다른 경우의 수 제거

 

앞에서 그래프 트리 풀다가

이런 수학.. 문제 (?)  푸니까 또 다르게 재밌는 것 같다

 

1회독	2회독	3회독	4회독	5회독
V	7/3

---

(참고)

✔ Do it 알고리즘 코딩테스트 자바편