[백준] 1010번 : 다리 놓기

1010번: 다리 놓기

[동적 프로그래밍 (메모제이션)]

특별한 방법이 사용되지는 않는 문제이다. 왼쪽의 사이트가 n개이고, 오른쪽의 사이트가 m개일 때 다리를 놓을 수 있는 경우의 수가 dp[n][m]이라면,

 

dp[1][1] = 1   dp[2][1] = 0   dp[3][1] = 0   dp[4][1] = 0

dp[1][2] = 2   dp[2][2] = 1   dp[3][2] = 0   dp[4][2] = 0

dp[1][3] = 3   dp[2][3] = 3   dp[3][3] = 1   dp[4][3] = 0

dp[1][4] = 4   dp[2][4] = 6   dp[3][4] = 4   dp[4][4] = 1

dp[1][5] = 5   dp[2][5] = 10 dp[3][5] = 10  dp[4][5] = 5

dp[1][6] = 6   dp[2][6] = 15 dp[3][6] = 20  dp[4][6] = 15

 

수의 규칙성이 드러난다.

 

dp[2][4]의 경우 dp[1][1] + dp[1][2] + dp[1][3]

dp[4][6]의 경우 dp[3][1] + dp[3][2] + dp[3][3] + dp[3][4] + dp[3][5]로 나타낼 수 있다.

# Code </>

public class Main {

    static int[][]dp;
    static void Dynamic(int n, int m){

        for(int i=1; i<=m; i++) dp[1][i] = i;

        for(int i=2; i<=n; i++)
            for(int j=1; j<=m; j++)
                for(int k=1; k<j; k++)
                    dp[i][j] += dp[i-1][k];

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());

        for(int i=0; i<t; i++){
            st = new StringTokenizer(br.readLine());

            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            dp = new int[30][30];

            if(n != m) {

                Dynamic(n, m);
                System.out.println(dp[n][m]);
            }
            else
                System.out.println(1);
        }
    }
}