본문 바로가기
코딩테스트/programming_JAVA

[Java] baekjoon_11050 : 이항 계수 1

by prometedor 2024. 1. 13.

수학, 구현, 조합론

이항 계수 1 : Bronze1

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

 

11050번: 이항 계수 1

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

www.acmicpc.net

 

 

 

풀이

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

public class Main21 {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());
    int ret = 1;

    for (int i = 1; i <= N; i++) {
      ret *= i;
    }
    
    for (int i = 1; i <= M; i++) {
      ret /= i;
    }

    for (int i = 1; i <= N - M; i++) {
      ret /= i;
    }

    bw.write(String.valueOf(ret));
    bw.newLine();
    bw.flush();
    bw.close();
  }
}

 

 

이항 계수

이항 계수(binomial coefficient)는 조합론에서 자주 사용되는 개념 중 하나이다. 이항 계수는 주어진 집합에서 원하는 개수의 원소를 선택하는 방법의 수를 나타낸다. 주로 "n 개 중에서 k 개를 선택하는 경우의 수"를 나타낼 때 사용된다.

이항 계수는 다음과 같이 표현된다.

여기서 은 팩토리얼(factorial)이며, 1부터 n까지의 모든 양의 정수를 곱한 값이다. 은 k 팩토리얼이며, (n-k)!은 n-k 팩토리얼이다.

이항 계수는 주로 조합(combination)의 경우의 수를 계산하는 데 사용되며, 이는 주어진 n개의 원소에서 k개의 원소를 순서에 상관없이 선택하는 방법의 수를 의미합니다. 이항 계수는 동적 계획법, 파스칼의 삼각형 등을 활용하여 효율적으로 계산할 수 있습니다.

 

 


 

 

문제점 : 이항 계수가 뭔지 몰랐다. ^-^;;

해결 방법 : 이항 계수에 대해 검색하여 알아보았다.

깨달은 바 : 이항 계수는 조합론에서 자주 사용되는 개념 중 하나이고, 주어진 집합에서 원하는 개수의 원소를 선택하는 방법의 수(n개의 원소에서 k개의 원소를 순서에 상관없이 선택하는 방법의 수)를 나타낸다.