백준 1010번 다리 놓기(JAVA,DP)

<풀이방식>

먼저 2차원 배열 DP를 선언한다. N =1 인 경우에는 M의 값이 곧 배열의 값이 되고 , N = M 이라면 배열의 값은 1이된다.
이러한 값을 먼저 채운 다음
dp[i][j] = dp[i-1][j-1] + dp[i][j-1] 라는 수식이 성립함을 찾았다. 최종적으로 dp[N][M] 의 값이 최대값이 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int tc = sc.nextInt();
		
		for(int i = 0 ; i < tc; i++) {
			int N = sc.nextInt();
			int M = sc.nextInt();
	
			int [][] dp = new int [N+1][M+1];
			
			//1행 값 세팅
			for(int j = 1 ; j < M+1; j ++) 
				dp[1][j] = j;
			
			//N ==M 이면 1이라고 세팅
			for(int j = 1 ; j < N+1 ; j++) {
				for(int k = 1 ; k < M+1 ; k++) {
					if(j==k)
						dp[j][k] = 1;
				}
			}
			
			//DP부분
			for(int j = 2 ; j<N+1; j++) {
				for(int k = j+1 ; k < M+1 ; k++) {
					//2차 배열에 값 채우다보면 다음과 같은 규칙이있음
					dp[j][k] = dp[j-1][k-1] + dp[j][k-1];				}
			}
			
			System.out.println(dp[N][M]);
		}
	}
}