[백준] 단계별로 풀어보기(단계:17,정수론 및 조합론,JAVA)11050번, 이항 계수 1

문제 링크

11050번: 이항 계수 1

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에서 규칙에 대한 알고리즘을 살펴보면 전에

이항계수란 이항정리로 전개하였을 때 조합의 가짓수를 나타내는 것으로공식은 nCm 일 때

n!/m!(n-m)!          0≤k≤n

0                        k<0

0                        k>n

예를 들어₄C₂ = 4!/2!(4-2)! = (4×3×2×1)/(2×1)(2×1) = 6

알고리즘을 살펴보면

n-m은 n!에서 무조건 약분이 되기 때문에 (n-m) < i ≤ n 범위의 값들을 곱한 후m!에 값들을 나눠주면 이항계수에 값을 구할 수 있습니다.위에 예를 들어보면

₄C₂ = (3×4)/(2×1) = 6으로 바로 나오게 됩니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해 띄어쓰기 기준으로 숫자를 나누어 저장하였습니다.
• 이항계수를 구하는 함수 binomialCoefficient를 만들었습니다.
• 함수를 통해 이항계수를 받아 BufferedWriter에 저장하였습니다.
• BufferedWriter을 사용하여 저장된 결과를 출력하였습니다.

• 위에 알고리즘을 토대로 binomialCoefficient을 구성하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	//BufferedWriter를 통해 결과 값 출력
        //--------입력값 저장--------------
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	int N = Integer.parseInt(st.nextToken());
    	int K = Integer.parseInt(st.nextToken());
    	
    	int result=binomialCoefficient(N, K);// 함수 실행
    	bw.write(result + "\n");	//결과 BufferedWriter에 저장
    	bw.flush();	//결과 출력
    	bw.close();
    	br.close();
	}
    //----------이항 계수 구하는 함수-----------
	public static int binomialCoefficient(int N, int K) {
    	int temp = N-K;
    	int result = 1;
    	
    	for(int i=temp+1;i<=N;i++)
    		result = result * i;
    	
    	for(int i=2;i<=K;i++)
    		result = result/i;
    	
    	return result;
	}
}