BOJ_S3_2407

📁 [S3_2407] 조합

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

public class Main {
	static StringTokenizer st;
	static long res;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br =  new BufferedReader(new InputStreamReader(System.in));
		
		st = new StringTokenizer(br.readLine(), " ");
		
		int n = Integer.parseInt(st.nextToken());
		
		int m = Integer.parseInt(st.nextToken());
		
        // n1,n2 1로 초기화
		BigInteger n1 = BigInteger.ONE;
		BigInteger n2 = BigInteger.ONE;
		
        // nCm 계산 = ( n * (n-1) * (n-2) .. * (n-m+1) ) / ( 1 * 2 * 3 .. * m )
		for(int i=0; i<m; i++){
			n1=n1.multiply(new BigInteger(String.valueOf(n-i)));
			n2=n2.multiply(new BigInteger(String.valueOf(i+1)));
		}
		
        // 마지막 나눠주기
		System.out.println(n1.divide(n2));

	    }
	}

🤔 나의 생각

처음에 범위가 너무 큰 수여서 고민했지만 마땅한 방법이 안 떠올라서 재귀로 조합을 짜서 했지만 시간초과가 떴다..
해결책을 못찾겠어서 좀 찾아보니 BigInteger를 써야하는 것이였다.
써본 기억이 없는 탓에 자료를 찾아봤는데 BigInteger는 byte와 String에서만 변경이 가능해서 수를 String으로 형변환 해주고 다시 BigInteger로 형변환을 해주었다.
그리고 곱하는 것이 multiply이고 나누는 것이 divide 였다.
어떻게 보면 간단한 문제였는데 BigInteger에 대해 잘 몰라서 못 풀었던 것 같다.
그리고 좀 찾아보다 조합 식으로 (n-1)C(m-1) + (n-1)Cm (재귀) 도 잘 알고 있으면 잘 사용 될 것 같다.

조합 식

• nCr = n! / (n-r)!r!
• nCr = n-1 C r-1 + n-1 C r -> 재귀적 표현
• nC0 = 1