[백준] 1010 다리 놓기 - DP JAVA

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

1010번: 다리 놓기

코드설명

DP 문제입니다.

 

M개의 사이트에서 N개의 사이트를 뽑는 조합을 이용합니다. 

순서는 중요하지 않으므로 다 뽑고 난 이후에 저절로 다리가 겹치지 않도록 바꿔주면 되므로 

조합을 구한다면, 다리가 겹치치 않게 설정할 수 있습니다.

 

파스칼 삼각형에서 조합의 규칙성을 이용합니다.

nCr = n-1Cr-1 + n-1Cr
 
nCr( n==r ) = 0,
nC0 = 0

 

 

코드

Bottom-Up, 배열을 활용한 코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int T;
	public static int answer = 0;
	public static int[][] dp;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	T = Integer.parseInt(st.nextToken());
    	dp = new int[31][31];
    	
    	//파스칼 삼각형의 nC0 , nCn 을 처리합니다. 
    	for(int i=0;i<30;i++) {
    		dp[i][i] = 1;
    		dp[i][0] = 1;
    	}
    	
    	//nCr = n-1Cr-1 + n-1Cr 을 구현합니다.
    	for(int i=2; i<30;i++) {
    		for(int j=1;j<30;j++) {
    			dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
    		}
    	}
    	
    	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(dp[M][N]);
    	}
    }
   
}

 

Top-Down, 재귀를 활용한 코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int T;
	public static int answer = 0;
	public static int[][] dp;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	T = Integer.parseInt(st.nextToken());
    	dp = new int[31][31];
    	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(combination(M, N));
    	}
    		
    	
    	
    }
    
    public static int combination(int n, int r) {
    	
    	//이미 계산된 값일 경우
    	if(dp[n][r] > 0) {
    		return dp[n][r];
    	}
    	
    	// n과 r 일경우 뽑는 방법은 무조건 1개입니다.
    	// r == 0일경우 하나도 뽑지 않기에 1개입니다.
    	// 파스칼 삼각형에서 맨끝과 맨끝을 의미합니다.
    	if(n == r || r == 0) {
    		return dp[n][r] = 1;
    	}
    	
    	//
    	else {
    		return dp[n][r] = combination(n - 1, r - 1) + combination( n - 1, r);
    	}
    	
    }
    
}