Baekjoon 2407 조합 JAVA

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

2407번: 조합

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%202407

 

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

 

해당 문제는 nCm 을 구하는 문제다.

​

처음에 범위가 100*100이길래 dp를 이용해서 풀면 되겠다 생각했고,

dp를 이용해 문제를 풀어 제출했더니

틀렸다고 나와서 반례를 찾아보던 중

​

100 50에 대해서

100891344545564193334812497256

라는 값이 나와야 하는데 이는 long 형도 벗어난다.

​

그래서 알아보던 중 자바의 BigInteger를 이용하면 해결 가능하다고 하여

BigInteger를 이용해 해결했다.

​

BigInteger는 숫자를 문자형으로 나타내에 거의 무한한 숫자를 표현할 수 있다고 한다.

​

dp를 그대로 이용하였고 단지 dp 배열을 BigInteger형으로 선언하고

연산하는 부분에서 add 메서드를 이용하여 문제를 해결했다.