[백준] 2407 - 조합 (Java)

Problem

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

Approach & Logic

1) 파스칼의 삼각형 원리 이용

nC0=1, nCn=1 이므로 if문을 사용하여 조건문을 만들고
나머지 경우(else)에는 nCr = n-1Cr-1 + n-1Cn라는 것을 이용한다.

2) 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
문제에서 n과 m의 범위가 5~100 이므로 대충 엄청 큰수가 예상되기 때문에 무한의 정수가 들어갈 수 있는 가능성이 있을때 사용하는 BigInteger를 사용하는 것이 좋다. (BigInteger은 java.math안에 있음)

• BigInteger 선언
  : BigInteger는 문자열 형태로 이루어져 있다.

  BigInteger bigNumber = new BigInteger("10000"); 

• BigInteger 계산
  : BigInteger는 문자열이기 때문에 사칙연산이 안되므로 BigInteger은 클래스 내부에 있는 메서드를 사용해야 한다.

  덧셈: bigNumber1.add(bigNumber2);
  뺄셈: bigNumber1.subtract(bigNumber2);
  곱셈: bigNumber1.multiply(bigNumber2);
  나눗셈: bigNumber1.divide(bigNumber2);
  나머지: bigNumber1.remainder(bigNumber2);

• BigInteger 형 변환

  int형으로 변환: bigNumber.intValue();
  long형으로 변환: bigNumber.longValue();
  float형으로 변환: bigNumber.floatValue();
  double형으로 변환: bigNumber.doubleValue();
  String형으로 변환: bigNumber.toString();

---

Code

package BaekJoon_java;

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

public class boj_2407 {
    
    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 || j == i) {
                    dp[i][j] = new BigInteger("1"); 
                } else {
                    dp[i][j] = dp[i-1][j-1].add(dp[i-1][j]);
                }
            }
        }
        
        System.out.println(dp[n][m]);
       
    }
}