[백준(Baekjoon)][자바(java)] 1010 : 다리 놓기 / 정수론 및 조합론

 

www.acmicpc.net/problem/1010

1010번: 다리 놓기

 

문제 풀이

 

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

public class Main {
	
	static int[][] dp; 

	static int bino( int n, int r ) {
		if( r == 0 || n == r ) return 1;
		if( dp[n][r] != -1 )
			return dp[n][r];
		return dp[n][r] = bino( n-1, r-1 ) + bino( n-1, r );
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		int t = Integer.parseInt( br.readLine() ), n, m, i, j;
		while( t-- > 0 ) {
			st  = new StringTokenizer( br.readLine() );
			n = Integer.parseInt( st.nextToken() );
			m = Integer.parseInt( st.nextToken() );
			dp = new int[m+1][n+1];
			for( i = 0; i < m+1; i++ )
				for( j = 0; j < n+1; j++)
					dp[i][j] = -1;
			sb.append( bino( m, n ) + "\n" );
		}
		br.close();
		System.out.println( sb.toString() );
	}
}

 

*  이항 계수

-  n <= m 이므로, m개 중 n개를 뽑는 조합의 경우의 수를 구하는 것과 같다