intro : 이항계수의 뜻은 조합의 개념에서 나오는 값으로, 주어진 N개의 원소 중에서 K개를 선택하는 방법의 수를 나타낸다.

문제

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

입력

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

출력

N K를 출력한다.

문제 풀이 (104ms)

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

public class Main {
    public static void main(String[] args) throws IOException {
        // 입출력을 위한 BufferedReader, BufferedWriter 객체 생성
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 입력값이 한줄로 5 2 공백값으로 들어오기에 StringTokenizer 객체를 통해 split
        StringTokenizer st = new StringTokenizer(br.readLine());
        int first = Integer.parseInt(st.nextToken());
        int second = Integer.parseInt(st.nextToken());

        // 조합의 계산을 위해서는 다음과 같은 계산 과정이 필요함
        int value1 = factorial(first); // n!에 해당함
        int value2 = factorial(first - second); // n-k!에 해당함
        int value3 = factorial(second); // k!에 해당함

        // 조합의 공식 계산
        int result = value1 / (value2 * value3); 

        // bw로 출력하기 위해 문자열로 변환 후 write
        bw.write(String.valueOf(result));
        bw.flush();

        // 자원 반납
        bw.close();
        br.close();
    }

    public static int factorial(int n) {
        // 초기 결과값은 1
        int result = 1;
        // 입력값이 0보다 큰 경우만 반복문 실행
        while (n > 0) {
            // 반복해서 곱하기 연산을 진행 (result * n)
            result *= n;
            n--;
        }
        // 결과값 return
        return result;
    }
}

문제 해석

사실 이항계수라는 단어 자체가 생소해서 무슨말인지 모르겠어서 문제를 못푸는 경우가 많은거 같은데, 나 또한 해당 단어를 검색해보고 나서야 문제가 무엇을 원하는지를 알 수 있었다. 결국 조합의 개념에 대한 문제를 묻는 문제였는데 N개 중에 K개의 조합을 구하는 문제를 바꿔 말할수 있는것이다. 그렇다면 조합의 경우의 수를 구하는 공식은 뭔지 알면 쉽게 풀 수 있다는 뜻이다.

조합의 경우의 수를 구하는 공식
공식 : nCr 
n! / (n-r)! * r!

위 공식을 현재 문제에 대입을 해보면 N! / (N-K)! * K! 을 계산하면 되는 문제이다.

I am visible

contact

문제

입력

출력

문제 풀이 (104ms)

문제 해석