(Java) 백준 11050번 - 이항 계수 1

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

문제

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

접근

이항계수란 주어진 N에 대해 K개를 뽑는 경우의 수를 말한다. 즉, 예제로 보면 1부터 5까지의 수 중 중복되지 않는 두가지 수를 뽑는 경우를 구하면 된다. 그래서 이를 재귀로 구현했다.

문제해결

> N과 K를 입력받고 재귀를 통해 이항계수(N, K)를 구하는 메소드 num을 호출한다.
> num은 인자로 인덱스, 즉 현재 뽑는 수와, 뽑은 수의 개수를 가진다. 그래서 1부터 시작하며 처음엔 0개를 뽑으므로 num(1, 0)으로 호출한다.
> 함수 내부에선 탈출 조건으로 K개 이상을 뽑았을 때, 가능한 경우라는 뜻이므로 cnt를 누적하고 재귀를 깨준다.
> 아니면 2개를 뽑기위해 인자로 들어온 idx부터 N까지를 돌며 하나씩 뽑고 
중복없이 재귀로 i+1을 idx로 가지며 뽑았던 카드의 수 +1로 들어간다.

코드

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

public class Main
{
    //11050번 이항계수1
    static int N, K;
    static int cnt = 0;
    static void num(int idx, int rst)
    {
        if(rst >= K)
        {
            cnt++;
            return;
        }
        for(int i = idx; i <= N; i++) num(i+1, rst+1);
    }
    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());

        num(1, 0);
        System.out.println(cnt);
    }
}

후기

이항계수가 뭔지 몰라서 개념을 공부했다. 의외의 부분에서 막혔다. 이항계수를 몰라서 이렇게 했지만 사실은 팩토리얼을 쓰면된다고 한다. 예제를 예로들면 5C2를 구하는 문제이므로 5!을 2! * 3!으로 나누면 된다. 즉, 팩토리얼 기능을 메소드로 구현하고 호출해주면 된다.
또 파스칼의 삼각형 성질을 이용한 DP로도 풀 수 있다고 한다.