[백준] 1010번 : 다리 놓기 자바(JAVA) 풀이 (DP)

문제

---

---

문제 탐색하기

이 문제는 조합과 DP 두 가지 방법으로 풀 수 있다. 여기서는 DP 방법으로 풀어보도록 하겠다. 

• N : 서쪽 사이트
• M : 동쪽 사이트

DP 설계하기

1. N = 1 일 때

N = 1 일 때, 총 다리를 놓을 수 있는 경우의 수는 M개 이다.

서쪽 N개 사이트, 동쪽 M개 사이트 일 때 놓을 수 있는 다리의 경우의 수를 F(N,M) 라 표시하면 

→  F(1,M) = M

2. N = 2 일 때

• M = 2 일 때, F(2,2) = F(1,1)

 

• M = 3 일 때, F(2,3) = F(1,2) + F(1,1,)

•  M = 4 일 때, F(2,4) = F(1,3) + F(1,2) + F(1,1)

3. N = 3 일 때

• M = 3 일 때, F(3,3) = F(2,2)

• M = 4 일 때, F(3,4) = F(2,3) + F(2,2)

 

=> F(N,M) = F(N-1, M-1) + F(N-1, M-2) + ... + F(N-1, N-1)

규칙이 있는 것을 알 수 있다. 

앞에서 미리 계산해 높은 값을 활용할 수 있고 동일한 계산식이 반복되므로 DP 사용가능하다. 

 

가능한 시간복잡도

입력 범위 ( 0 ＜ N ≤ M ＜ 30)

N개 M개의 경우의 수를 구해야함으로 시간 복잡도는 O( N )*O( M )

---

코드 설계하기

• N,M에 대한 값을 입력받는다.
• 값을 저장할 배열 bridge를 선언한다.
• 가장 작은 문제의 답이 N=1 이므로 F(1,M) = M 에 대한 답을 저장한다.
• F(N,M) = F(N-1, M-1) + F(N-1, M-2) + ... + F(N-1, N-1) 에 대한 코드를 작성한다.
• 결과값을 출력한다. 

---

풀이 코드

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

public class Main {	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine()); // 테스트케이스
		
		for(int t=0;t<T;t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken()); // 서쪽 사이트 개수
			int M = Integer.parseInt(st.nextToken()); // 동쪽 사이트 개수
			
			int[][] bridge = new int[N+1][M+1];
			
			// 가장 작은 문제의 답 구하기 
			// F(1,M) = M
			for(int i=1;i<M+1;i++) {
				bridge[1][i] = i;
			}
			
          	// F(N,M) = F(N-1, M-1) + F(N-1, M-2) + … + F(N-1,N-1)
			for(int i=2;i<N+1;i++) { // 2부터 N까지
				for(int j=1;j<M+1;j++) { // 1부터 M까지
					for(int k=i-1;k<j;k++) { // N-1 부터 M-1까지 
						bridge[i][j] += bridge[i-1][k];
					}
				}
			}
			
			System.out.println(bridge[N][M]);
			
			
		}
		
	}
}