[백준 1010번] 다리 놓기

https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

 

 

N의 첫번째 요소를 배정하는 위치하고 나서 나머지 N-1와 M-1에 대해서 부분구조를 발견할 수 있다.

 

점화식은 

dp[n][m] = dp[n-1][1] + dp[n-1][2] ... + dp[n-1][m-1]  이다.  

 

 

재귀 ver

package backjoon.p1010;

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

public class Main {
    static int T,N,M;
    static long[][] dp;
    public static void main(String[] args) throws IOException {
//	BufferedReader br = new BufferedReader(new FileReader("testcase.txt"));
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	T = Integer.parseInt(br.readLine());
	dp = new long[30][30];
	for (int i = 1; i < 30; i++) {
	    dp[1][i] = i;
	}
	for (int testcase = 0; testcase < T; testcase++) {
	    String[] input = br.readLine().split(" ");
	    N = Integer.parseInt(input[0]); M = Integer.parseInt(input[1]);

	    long ret = solve(N, M);
	    System.out.println(ret);
	}
    }

    private static long solve(int n, int m) {
        if(n == 1) return dp[n][m];
        if(dp[n][m] != 0) return dp[n][m];

    	long ret = 0;
	for (int i = 1; i < m; i++) {
	    ret += solve(n-1, i);
	}
	dp[n][m] = ret;
    	return dp[n][m];
    }
}

 

 

for문 version

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int T,N,M;
    static long[][] dp;
    public static void main(String[] args) throws IOException {
//	BufferedReader br = new BufferedReader(new FileReader("testcase.txt"));
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	T = Integer.parseInt(br.readLine());

	dp = new long[30][30];
	for (int i = 1; i < 30; i++) {
	    dp[1][i] = i;
	}
	solve(29, 29);
	for (int testcase = 0; testcase < T; testcase++) {
	    String[] input = br.readLine().split(" ");
	    N = Integer.parseInt(input[0]); M = Integer.parseInt(input[1]);

	    System.out.println(dp[N][M]);
	}
    }

    private static long solve(int n, int m) {
	if(dp[n][m] != 0) return dp[n][m];

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

	return dp[n][m];
    }
}