[1328] 고층 빌딩

✔ 고층 빌딩

[백준 1328]

문제 분석하기

가장 큰 빌딩을 마지막에 배치하면 중간 위치에 배치할 경우가 복잡하므로 반대로 가장 작은 빌딩을 N번째 배치하여 문제에 접근

1) 가장 작은 빌딩을 왼쪽 위치에 배치한 경우 : 왼쪽에서 보는 빌딩의 수 1 증가

2) 가장 작은 빌딩을 오른쪽 위치에 배치한 경우 : 오른쪽에서 보는 빌딩의 수 1 증가

3) 가장 작은 빌딩을 가운데 위치에 배치한 경우 : 양쪽에서 보는 빌딩의 수가 증가하지 않음

손으로 풀어보기

1. 점화식의 형태와 의미를 도출
   • D[N][L][R]은 N개의 빌딩이 있고 왼쪽에서 L개, 오른쪽에서 R개가 보일 때 가능한 경우의 수
2. 점화식을 구함
   • N - 1개의 빌딩에서 왼쪽에 빌딩을 추가할 때는 왼쪽 빌딩이 1개 증가하므로 이전 경우의 수는 D[N - 1][L - 1][R]
   • N - 1개의 빌딩에서 오른쪽에 빌딩을 추가할 때는 오른쪽 빌딩이 1개 증가하므로 이전 경우의 수는 D[N - 1][L][R - 1]
   • N - 1개의 빌딩에서 가운데 빌딩을 추가할 때는 증가 수가 없지만,
     N - 2개의 위치(왼, 오 제외)에 배치할 수 있으므로 N - 2를 곱하면 D[N - 1][L][R] * (N - 2)
   • 그러므로 위의 3가지 경우의 수를 모두 더하면
     D[N][L][R] = D[N - 1][L - 1][R] + D[N - 1][L][R - 1] + D[N - 1][L][R] * (N - 2)
3. 점화식으로 D 배열을 채운 후 D[N][L][R]의 값을 출력

예) 3개의 빌딩이 있고 왼쪽에서 2개, 오른쪽에서 2개가 보일 때 가능한 경우의 수

D[3][2][2]	D[2][1][2] + D[2][2][1] + D[2][2][2] * (3 - 2)
D[2][1][2]	D[1][0][2] + D[1][1][1] + D[1][1][2] * (2 - 2) = 1
D[2][2][1]	D[1][1][1] + D[1][2][0] + D[1][2][1] * (2 - 2) = 1
D[2][2][2]	건물이 2개일 때 양쪽에서 2개의 건물이 모두 보일 수 없으므로 0
D[3][2][2]	D[2][1][2] + D[2][2][1] + D[2][2][2] * (3 - 2) = 1 + 1+ 0 = 2

슈도코드 작성하기

D[N][L][R] (빌딩 N개를 왼쪽에서 L개, 오른쪽에서 R개가 보이도록 배치할 수 있는 모든 경우의 수)
D[1][1][1] = 1
for(i -> 2 ~ N) {
    for(j -> 1 ~ L) {
        for(k -> 1 ~ R) {
            D[i][j][k] = D[i - 1][j - 1][k] + D[i - 1][j][k - 1] + D[i - 1][j][k] * (i - 2)
            나온 결과를 1000000007 나머지 연산 수행하기
        }
    }
}
D[N][L][R]값 출력하기

코드 구현하기

/**
 * 1328) 고층_빌딩
 */
public class D092_1328 {
    static int N, L, R;
    static long D[][][];
    static long mod = 1000000007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // N(빌딩의 개수)
        N = sc.nextInt();
        // L(가장 왼쪽에서 봤을 때 보이는 빌딩의 수)
        L = sc.nextInt();
        // R(가장 오른쪽에서 봤을 때 보이는 빌딩의 수)
        R = sc.nextInt();
        // D[N][L][R] (빌딩 N개를 왼쪽에서 L개, 오른쪽에서 R개가 보이도록 배치할 수 있는 모든 경우의 수)
        D = new long[101][101][101];
        // 건물이 1개일 때 배치될 경우의 수는 1개
        D[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++) {
                    D[i][j][k] = (D[i - 1][j - 1][k] + D[i - 1][j][k - 1] + D[i - 1][j][k] * (i - 2)) % mod;
                }
            }
        }
        // D[N][L][R]값 출력하기
        System.out.println(D[N][L][R]);
    }
}