백준 JAVA11 11050번 : 이항 계수 1

이항 계수 1

시간 제한	메모리 제한
1 초	256 MB

문제

자연수 N과 정수 K가 주어졌을 때 이항 계수 (NK)를 구하는 프로그램을 작성하시오.

입력

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

출력

(NK)를 출력한다.

예제 입력 1

5 2

예제 출력 1

10

출처

• 문제를 만든 사람: baekjoon

Idea.

• 이항계수 ex) 5개에서 2개를 뽑는 경우의 수
• 4개는 선택이 문제가 해결된 데이터로 가정
  • 마지막 데이터가 선택이 안됐을 경우 → D[4][3]
  • 마지막 데이터가 선택됐을 경우 → D[4][2]
• 점화식
  • D[5][2] = D[4][3] + D[4][2]
• DP 배열 초기화
  • 공통적인 경우의 수를 배열에 넣어준다.
  • D[i][1] = i (i개 중 1개를 뽑는 경우의 수는 i개) ex) 5개중 1개를 뽑는 경우의 수 5개
  • D[i][0] = 1 (i개 중 1개도 선택하지 않는 경우의 수는 1개) ex) 5개중 0개를 뽑는 경우의수 1개
  • D[i][i] = 1 (i개 중 i개를 선택하는 경우의 수는 1개) ex) 5개중 5개를 뽑는 경우 1개

Code.

package combination;

import java.util.Scanner;

public class P11050_binomialCoefficient {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt(); // 총 개수
		int K = sc.nextInt(); // 선택의 수

		int[][] DP = new int[N + 1][N + 1];
		for (int i = 0; i <= N; i++) {
			DP[i][i] = 1;
			DP[i][0] = 1;
			DP[i][1] = i;
		}
		
		//점화식 bottom-up
		for (int i = 2; i <= N; i++) { //1은 위에서 모두 채워줌 
			for (int j = 1; j < i; j++) { //고르는 수의 개수가 전체 개수를 넘을 수 없다. 
				DP[i][j] = DP[i-1][j] + DP[i-1][j-1]; 
			}
		}
		System.out.println(DP[N][K]);
	}

}