[Java] 백준 1010번 (다리놓기)

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

1010번: 다리 놓기

N구역에서 M구역으로 다리를 건설한다. (N <= M)

문제에서 N 구역에서 M 구역으로 다리를 건설한다고 하니 N을 기준으로 생각하기 쉽다. (나도 그랬다.)

반대로 M을 기준으로 생각하면 실마리가 보인다.

M구역에서 N구역의 갯수만큼 연결할 수 있는 경우의 수를 구하면 되기 때문이다.

더 나아가, 서로 다른 다리는 겹칠 수 없다하니 순서가 있는 뽑기, 즉 조합을 사용해서 풀어야 한다.

예를들어, 5(M)개중에 3(N)개를 뽑아야 한다면

를 계산해야 한다.

계산식은

​​이렇게 된다.

 

하지만 수 범위 제한이 30 이므로 무턱대고 팩토리얼 (!) 을 연산하면 long의 범위를 훌쩍 넘어간다.

이럴 때 dp, 동적 계획법을 이용해 풀 수 있다.

​

조합 계산은 아래와 같이 표현할 수 있다.

​

 

아래의 그림들을 보면 이해가 더 쉬울 것이다.

 

​

​

이 계산식을 보고 배열을 이용한 dp를 사용해서 풀었다.

​

​

아래는 정답 코드이다.

import java.io.*;
import java.util.StringTokenizer;
 
public class Main {
	
	private static final int MAX = 31;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		//init
		StringTokenizer st;
		int n = 0 , m = 0;
		StringBuilder sb = new StringBuilder();
		int dp [][] = new int[MAX][MAX];
		
		
       // 2C2 == 2C0 == 1 성질
		for(int i = 1 ; i < MAX ; i++) {
			dp[i][0] = 1;
			dp[i][i] = 1;
		} 
		
		for (int i = 2; i < MAX; i++) {
			for (int j = 1; j < MAX; j++) {
				dp[i][j] = dp[i-1][j-1] + dp[i-1][j]; 
			}
		}
				
		//impl
		for (int i = 0; i < T ; i++) {
			st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
 
			if(i != T-1) {
				sb.append(dp[m][n]).append("\n");
			}else {
				sb.append(dp[m][n]);
			}
			
			
		} // for
 
		
		System.out.println(sb.toString());
	} 
} // class