[자바] 백준 2407번: 조합

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

2407번: 조합

nCr=n-1Cr-1 + n-1Cr

nCn=nC0=1

 

이 두 공식을 이용해서 풀었다.

 

재귀함수만 이용하게되면 너무 오래걸리거나 스택오버플로우가 날 수 있어서

이차원배열을 하나 만들어 둔 다음

한번 계산한 값은 배열에 저장해두고, 나중에 같은 값을 써야할 때 배열에서 바로 꺼내쓸 수 있도록 하였다.

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

public class P2407 {
	static BigInteger[][] note;

	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());

		note = new BigInteger[n + 1][m + 1];

		System.out.println(combination(n, m).toString());
	}

	static BigInteger combination(int n, int m) {
		if (note[n][m] != null) {
			return note[n][m];
		}

		if (n == m || m == 0) {
			return note[n][m] = BigInteger.ONE;
		}

		return note[n][m] = combination(n - 1, m - 1).add(combination(n - 1, m));
	}

}