[백준] 1010 다리 놓기

www.acmicpc.net/problem/1010

1010번: 다리 놓기

2021-01-27

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main1010 {
    public static int N, M;
    public static long dp[][];
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine().trim());
        int test = Integer.parseInt(st.nextToken());
        dp = new long [31][31];
        for(int i = 1; i <= 30; i++) dp[1][i] = i;
        for(int i = 2; i <= 30; i++) {
            for(int j = i; j <= 30; j++) {
                if(i == j) dp[i][j] = 1;
                else {
                    for(int k = i-1; k < j; k++) {
                        dp[i][j] += dp[i-1][k];
                    }
                }
            }
        }
        for(int ts = 1; ts <= test; ts++) {
            st = new StringTokenizer(bf.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            System.out.println(dp[N][M]);
        }
    }
}
 

 

#문제풀이

 

1. N이 1일 때는 M이 어떠한 값이 오든 M의 경우의 수를 갖는다. 

 

2. N이 2이상일 때는 N과 M의 값이 같은 경우에는 무조건 1을 경우의 수로 갖는다. 

 

3. 그 외의 경우, 다음과 같은 규칙을 갖는다.

 

dp[N][M] = dp[N-1][N-1] + dp[N-1][N] + .... + dp[N-1][M-1]