[백준/JAVA] 11050번: 이항 계수 1

🔺 문제

11050번: 이항 계수 1

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, K;    // 총 개수, 선택 개수
    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()," ");
        
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        // DP 배열 초기화
        D = new int[N + 1][N + 1];
        for(int i = 0 ; i <= N ; i++) {
            D[i][1] = i;    // i개에서 1개  선택하는 경우의 수  - i개
            D[i][0] = 1;    // i개에서 1개도 선택하지 않는 경우 - 1개
            D[i][i] = 1;    // i개에서 모두 선택하는 경우       - 1개
        }
        
        // DP 배열 값 채우기
        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];  // 조합 점화식
            }
        }
        
        System.out.println(D[N][K]);
        br.close();
    }
}

✅ 해결 아이디어
✔ 조합 문제 → 점화식 (파스칼의 법칙)이용

 

💥 유의사항

배열, 인덱스 범위 신경쓰기

⇨ 배열 크기가 N이 아니고 N+1이어야 함.

⇨ 점화식으로 배열 완성할 때 인덱스도 유의하기. (Bottom-UP 방식 사용)

    •  i : 1은 채워놔서 2부터 시작. 

    •  j : 0은 채워놔서 1부터 시작.

 

---

🔺 다른 풀이들

[백준] 11050번 : 이항 계수 1 - JAVA [자바]

정리 최고....👍👍👍

 

---

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

---

(참고)

 

 

[조합] nCr 쉽게 구하기. (수정 20190604)