[백준] 2407 - 조합 (Java)

[백준] 2407 - 조합 (Java)

문제

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

풀이/후기

BigInteger 연산 주의!!

확률과 통계 이슈로 순열과 조합부터 복습이 필요했다..^^;

여기서 nPr은 반복문을 돌며 N-i을 곱하는 것으로 표현하고

r!은 i+1을 곱하는 것으로 표현

반복문을 마치면 그 결과를 나눠주면 됨

 

(다이나믹프로그래밍으로 풀기)

파스칼의 삼각형을 이용하여 풀이할 수 있다.

이차원 배열을 이용하여 파스칼 삼각형을 표현한다.

코드

package DynamicProgramming;

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

public class Problem2407 {
	
	static BigInteger[][] bi = new BigInteger[100+1][100+1];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer str = new StringTokenizer(br.readLine(), " ");

		int N = Integer.parseInt(str.nextToken());
		int M = Integer.parseInt(str.nextToken());

		BigInteger sum = BigInteger.ONE;
		BigInteger div = BigInteger.ONE;

		for (int i = 0; i < M; i++) {
			sum = sum.multiply(new BigInteger(String.valueOf(N - i)));
			div = div.multiply(new BigInteger(String.valueOf(i + 1)));
		}

		System.out.println(sum.divide(div));
		dpFunc(N,M);			//DP를 이용한 풀이

	}

	
	static void dpFunc(int N, int M) {
		for (int i=1;i <= N; i++) {
			for (int j=0; j <= i; j++) {
				if (j==0 || j == i) {
					bi[i][j] = BigInteger.ONE;
				} else {
					bi[i][j] = bi[i-1][j].add(bi[i-1][j-1]);
				}
			}
		}
		
		System.out.println(bi[N][M]);
	}
}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/844d6889e70b83836f05580777f7bb0b714dcd1d

참고

https://mathbang.net/547#gsc.tab=0

https://dy-coding.tistory.com/entry/%EB%B0%B1%EC%A4%80-2407%EB%B2%88-%EC%A1%B0%ED%95%A9-java

https://www.crocus.co.kr/622