[백준 - 1010번] 다리 놓기 - 자바(JAVA) 정리 및 해설 & 1일 1DP - 1일차

안녕하세요. 오늘 풀어볼문제는 백준 다리 놓기입니다. 이 문제는 다이나믹 프로그래밍 혹은 조합으로 문제를 푸는 문제입니다. 

 

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

1010번: 다리 놓기

 

일단 이문제에서 결국 포인트로 잡아야하는 부분은 얼만큼 최대한 많은 여러가지의 경우의 수를 체크할 수 있냐라는 포인트입니다.

 

예시를 들어서 설명해보겠습니다. 

한점에서 3점으로 만들 수 있는 경우의 수는 3가지입니다.  근데 저희가 문제가 되는 것은 N개의 점일때 M개의 점을 따져야한다는 점이죠.

 

그랬을때 이해하기 쉬운 범주는 결국 1점을 기준으로 삼아서 여러가지의 경우로 쪼개서 생각해보는겁니다.

 

위와 같은 예시로 2-4는 한점을 연결 시켜놓고 나면-> 1-3짜리  모양으로 나눠버릴 수 있다는 것이죠.

즉, 1-3 짜리를 경우의 수를 알고 있다면, 굳이 제가 직접 경우를 다 세가면서 경우를 알 필요가 없다는 것입니다. 

 

이런 부분에서 DP의 개념을 사용할 수 있게되는데요. DP의 중복된 계산 감소가 나옵니다.  즉, 1-3을 계산을 더하는 게 아닌, 1-3의 경우의 수를 바로 대입하여 그 계산하는 시간을 줄이는 거죠.

 

 

하지만 하나더  고민해야할 부분이 있습니다. 첫번째로 선택해야할 점이 나머지 선택할 점의 갯수만큼은 남아있어야합니다.

위의 경우처럼 한 점이 연결되지 못한다면 최대한 많은 다리를 연결할 수 없는 경우이므로, 이런 케이스가 없게끔 아래처럼 마지막 경우는 남은 점 갯수와 연결해야하는 점의 갯수가 동일해야합니다.

 

 

 

 

이를 바탕으로 점화식을 대략적으로 세워본다면,

for(int t=j-1; t>i-2; t--){

dp[i][j] +=dp[i-1][t];

}

맨위의 경우 한개를 뺀 나머지 모든 경우를 남는 점 갯수 = 연결점 갯수일때까지 다 더해버리면 됩니다.

 

대신 Bottom - up 방식으로 진행해야하므로 경우의 수는 왼쪽 점 2개일때부터 시작해서 -> 30개일때까지 쭉 이런 반복적인 루프를 지속합니다. 

 

 

package codeBaekJoon;

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

public class No1011_Bridge {
	static long [][] dp = new long[31][31];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st;
		for(int i=1; i<31; i++){
			dp[1][i] = i;
		}
		for(int i=2; i<31; i++){
			for(int j=i; j<31; j++){
				if(i==j){
					dp[i][j] = 1;
				}
				else if(j-i==1){
					dp[i][j] = dp[i-1][j-1]+dp[i-1][j-2];
				}
				else{
					for(int t=j-1; t>i-2; t--){
					dp[i][j] +=dp[i-1][t];
					}
				}
				
			}
		}
		for(int i =0; i<n; i++){
			String tc = br.readLine();
			st = new StringTokenizer(tc , " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			System.out.println(dp[a][b]);
		}
	}
}