👀 문제
https://www.acmicpc.net/problem/2407
👊 도전
1. 설계
- DP를 이용해 nCr을 계산한다.
- long 형태를 초과하므로 BigInteger를 이용한다.
2. 구현 (성공 코드)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.*;
import java.math.BigInteger;
/**
* @author HEESOO
*
*/
class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
BigInteger[][] dp=new BigInteger[101][101];
dp[1][0]=dp[1][1]=BigInteger.ONE;
for(int i=2;i<=100;i++) {
for(int j=0;j<=i;j++) {
if(j==0 || i==j) dp[i][j]=BigInteger.ONE;
else dp[i][j]=dp[i-1][j].add(dp[i-1][j-1]);
}
}
System.out.println(dp[n][m]);
}
}
3. 결과
🤟 성공 🤟
4. 설명
- nCr을 DP를 이용해 계산한다
- C(n,r)=C(n-1,r)+C(n-1,r-1)
- dp[0][0]=dp[1][0]=dp[1][1]=0으로 초기화하고, i는 2부터 100까지, j는 i보다 더 클 수는 없으므로 j<=i인 범위를 구한다.
- j==0이거나 i==j인 경우에는 1이다.
- BigInteger형을 사용한다
- n=100, m=49이면 long형을 초과한다. 따라서 자바에서 가장 큰 BigInteger형을 사용해야한다.
- BigInteger에 숫자 1을 넣기 위해서는 BigInteger.ONE을 사용해야 한다.
- 덧셈 역시 +가 아닌, add()메소드를 사용한다. a+b는 a.add(b)와 같다.