[백준] 알고리즘 분류(수학,JAVA)2407번, 조합

문제 링크

 

2407번: 조합

---

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. nCm의 대한 계산을 진행합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. DP[]를 통해서 1~N까지의 팩토리얼에 대한 값을 저장합니다.

 

3. nCm에 계산을 진행하여 결과를 출력합니다.

 

 

 

팩토리얼 계산!

 

nCm을 계산하기 위해서는 n 이하의 팩토리얼의 값들을 가져야해서 DP[]에 값을 저장합니다.

 

nCm 계산 점화식 : n! ÷ ((n - m)! × m!)

 

Java의 long, int형은 최대값 100!의 값을 저장할 수 없기 때문에 BigInteger를 사용하였습니다.

 

제가 정리한 BigInteger에 대한 내용이니 참고해주시면 감사하겠습니다.

[JAVA] 큰 정수(숫자) 다루는 방법 BigInteger

 

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 100

M : 6

 

2. DP[]를 통해서 1~N까지의 팩토리얼에 대한 값을 저장합니다.

 

DP[1 ~ 100]까지 계산!

 

DP[1] = 1

DP[2] = 2

DP[3] = 6

DP[4] = 24

DP[5] = 120

.....

 

3. nCm에 계산을 진행하여 결과를 출력합니다.

 

nCm  =  n! ÷ ((n - m)! × m!)

= DP[n] ÷ (DP[n-m] × DP[m])

= DP[100] ÷ (DP[94] × DP[6])

= 1192052400

 

1192052400 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 N과 M을 띄어쓰기 기준 나누었습니다.
• DP[]에 1~N까지의 팩토리얼 값을 저장합니다.
• nCm의 점화식과 DP[]를 이용하여 계산한 결과를 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

결과코드

 

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

public class Main{
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        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());
        BigInteger[] DP = new BigInteger[N+1];
        DP[1] = BigInteger.valueOf(1);
        //1 ~ N까지 팩토리얼의 DP[]에 저장!
        for(int i=2;i<=N;i++)
            DP[i] = DP[i-1].multiply(BigInteger.valueOf(i));
        //nCm에 대한 점화식으로 계산!
        BigInteger answer = DP[N].divide(DP[M]).divide(DP[N-M]);
        bw.write(answer + "");	//조합의 계산결과 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();

    }
}