[JAVA] 백준 11050 이항 계수 1

11050번: 이항 계수 1 (acmicpc.net)

11050번: 이항 계수 1

 

 

풀이 과정 

 

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

 

이항 계수(Binomial Coefficeient)

 

이항 계수(Binomial Coefficient)를 구하는 다양한 알고리즘 | kbhetrr

Kbhetrr

 

- 이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수 

 

 

 Divide and Conquer

 

- 이항 계수의 두가지 성질을 이용해 재귀적으로 분할 정복을 수행

 

 

static int bino_dnc(int n, int k)
{
    if(k==0 || k==n) return 1;
    return bino_dnc(n-1, k) + bino_dnc(n-1,k-1);
}

 

 

정답 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    
    static int bino_dnc(int n, int k)
    {
        if(k==0 || k==n) return 1;
        return bino_dnc(n-1, k) + bino_dnc(n-1,k-1);
    }

    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 k = Integer.parseInt(st.nextToken());
        
        bw.write(bino_dnc(n,k)+"");
        
        bw.flush();
        bw.close();
        
        
    }
}