[백준 1010] 다리 놓기

 

 

각 다리의 수에 따른 경우의 수를 이용하여 풀어야 한다.

 

n       /       m	1	2	3	4	5	6
1	1	2	3	4	5	6
2	X	1	3	6	10	15
3	X	X	1	4	10	20

 

n이 1일땐 m의 수만큼 경우의 수가 증가한다.

n이 2일땐 m이 증가함에 따라 dp[n][m] = dp[n][m-1] + dp[n-1][m-1] 의 형식으로 증가하는걸 볼 수 있다.

n이 3일때도 마찬가지이다.

 

n이 1일때의 초기값과 n == m 일때의 초기값을 배열에 대입해주고

위 점화식을 이용하여 풀면된다.

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        long dp[][] = new long[30][30];
        for(int i=1; i<=29; i++)
            dp[1][i] = i;
        for(int i=1; i<=29; i++)
            dp[i][i] = 1;
        
        for(int i=2; i<=29; i++) {
            for(int j=i+1; j<=29; j++) {
                dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
            }
        }
        
        int t = sc.nextInt();
        while(t-->0) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            System.out.println(dp[n][m]);
        }
    }
}

 

 

코드에서는 long 배열을 선언했는데 int 로도 충분히 구현되는 범위이다.