백준 2407번 : 조합(Java)

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

1172번: 선인장 Automorphisms

 

---

[풀이]

 

- 다이나믹 프로그래밍 유형의 문제입니다.
- 먼저, 숫자의 범위가 int, long, BigInteger 어디에 속하는지 유의해야 합니다.
  - int 범위 : -2,147,483,648 ~ 2,147,483,647
  - long 범위 : -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807
  - BigInteger : 인자의 타입은 문자열이며 숫자의 범위는 무한합니다.
- 조합의 식을 파악해야 합니다.
  - nCm = n-1Cm-1 + n-1Cm
- 위 식을 토대로 dp 배열에 값을 채워서 요청하는 값을 반환합니다.

 

 

---

[코드]

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		BigInteger[][] dp = new BigInteger[101][101];
		
		for(int i = 1; i <= n; i++){
			for(int j = 0; j<= i; j++){
				if(j == 0 || i == j){
					dp[i][j] = new BigInteger(String.valueOf(1));
				}else{
					dp[i][j] = dp[i-1][j-1].add(dp[i-1][j]);
				}
			}
		}
		
		System.out.println(dp[n][m]);
	}
}