[백준] 1010 다리 놓기

package baekjoon;

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

public class Main_1010 {
    static int[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            dp = new int[N+1][M+1];
            for (int j = 1; j <= N; j++) {
                for (int k = 1; k <= M; k++) {
                    if(j<=k) {
                        dp(j, k);
                    }
                }
            }

            System.out.println(dp[N][M]);
        }
    }
    static void dp(int N, int M) {
        if(N==1) {
            dp[N][M] = M;
        } else if(N==M) {
            dp[N][M] = 1;
        } else {
            int sum = 0;
            int n = N;
            int m = M;
            while(true) {
                sum += dp[n-1][m-1];
                //System.out.println("dp["+N+"]["+M+"] += dp["+(n-1)+"]["+(m-1)+"]"+dp[n-1][m-1]);
                if(n-1 == m-1) {
                    break;
                }
                m--;
            }
            dp[N][M] = sum;
        }
        //System.out.println(N+" "+M+" "+dp[N][M]);
    }
}

N이 1이면 M의 갯수만큼 다리를 놓을 수 있고, N과 M이 같으면 각각 연결해야하므로 한가지밖에 방법이 없기 때문에 두 가지는 일단 예외 처리해주었다.
(N은 M보다 무조건 작고 다리는 겹칠 수 없다!)

일단 작은 수부터 점을 찍어 수를 세어봤는데 위에서부터 차례로 아래점과 연결하면 이미 연결했던 다리 경우의 수가 나온다. 그걸 합해주면 됨..
ex. 3 5 일 때 맨 위를 일직선으로 연결하면 아래에는 2 4 가 남음. 두번째와 일직선으로 연결하면 2 3 이 남음. 세번째와 일직선으로 연결하면 2 2 가 남음. 이 세가지 경우의 수를 합치면 3 5의 다리 연결 갯수가 나온다.

왜 2 2 까지나면 3개가 모두 연결되어야 하니까 맨 위를 제외하고 각각 연결될 수 있는 수까지는 남겨둔다..

이거 정말 풀이가 개판인데 밑에 그림을 보면 좀 이해가 쉬울 수도..
아무튼 dp 문제 하나 완!!

풀이는..노가다