[백준] 고층 빌딩

참고 : www.acmicpc.net/problem/1328

1328번: 고층 빌딩

 

 

- dp 문제

- 풀이를 보고 풀었다. 아이디어를 찾기가 힘들었다.

- dp[N][L][R] : dp[N-1][L][R] * (N-2) + dp[N-1][L-1][R] + dp[N-1][L][R-1];

 

import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int L = sc.nextInt();
        int R = sc.nextInt();
        long[][][] dp = new long[101][101][101];

        dp[1][1][1] = 1;

        for (int i = 2; i <= N; i++) {
            for (int j = 1; j <= L; j++) {
                for (int k = 1; k <= R; k++) {
                    dp[i][j][k] = (i-2) * dp[i-1][j][k] % 1000000007 +
                                    dp[i-1][j-1][k] % 1000000007 +
                                    dp[i-1][j][k-1] % 1000000007;
                    dp[i][j][k] %= 1000000007;
                }
            }
        }

        System.out.println(dp[N][L][R] % 1000000007);
    }
}