[자바] 백준 1010번: 다리 놓기

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

1010번: 다리 놓기

 

문제는 간단히

n,r을 입력받아 nCr을 출력하면 된다.

 

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

public class P1010 {

	static int[][] dp = new int[31][31];

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		for (int i = 0; i < T; i++) {
			st = new StringTokenizer(br.readLine());
			
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());

			System.out.println(combi(m, n));
		}
	}

	static int combi(int n, int r) {

		if (dp[n][r] > 0) {
			return dp[n][r];
		} else if (n == r || r == 0) {
			return dp[n][r] = 1;
		} else {
			return dp[n][r] = combi(n - 1, r - 1) + combi(n - 1, r);
		}
	}

}

nCn=nC0=1

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

 

조합의 특성 두가지를 이용하면 되는데,

nCr을 그냥 계산하면 똑같은 계산을 여러번 하게돼서 시간이 오래 걸린다.

미리 dp[31][31]을 만들어 두고, 계산 한 nCr은 dp[n][r]에 저장해 계산을 한 번씩만 하도록 하면 시간단축을 할 수 있다.