BOJ 1328 고층 빌딩

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

문제

상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았고, 집에 돌아오는 길에는 가장 오른쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았다.

상근이는 가장 왼쪽과 오른쪽에서만 빌딩을 봤기 때문에, 빌딩이 어떤 순서로 위치해있는지는 알 수가 없다.

빌딩의 개수 N과 가장 왼쪽에서 봤을 때 보이는 빌딩의 수 L, 가장 오른쪽에서 봤을 때 보이는 빌딩의 수 R이 주어졌을 때, 가능한 빌딩 순서의 경우의 수를 구하는 프로그램을 작성하시오.

예를 들어, N = 5, L = 3, R = 2인 경우에 가능한 빌딩의 배치 중 하나는 1 3 5 2 4이다.

---

입력

첫째 줄에 빌딩의 개수 N과 가장 왼쪽에서 봤을 때 보이는 빌딩의 수 L, 가장 오른쪽에서 봤을 때 보이는 빌딩의 수 R이 주어진다.

---

출력

첫째 줄에 가능한 빌딩 순서의 경우의 수를 1000000007로 나눈 나머지를 출력한다.

---

제한

• 1 ≤ N ≤ 100
• 1 ≤ L, R ≤ N

---

예제 입력 1

3 2 2

예제 출력 1

2

예제 입력 2

3 2 1

예제 출력 2

1

---

코드

DP 문제는 반복되는 규칙을 찾아 작은 단위의 문제로 나누어 해결하는데, 문제는 그 반복되는 규칙을 찾는 게 힘든 것 같다.

이번 문제도 코드 작성은 별로 시간이 걸리지 않았지만, 코드의 주된 알고리즘이 되는 규칙을 찾는 것에 많은 시간이 걸렸다.

위의 문제에 나온 것처럼 n이 빌딩 수, l이 가장 왼쪽에서 봤을 때 보이는 빌딩의 수, r이 가장 오른쪽에서 봤을 때 보이는 빌딩의 수라고 했을 때 n, l, r인 경우는 3가지의 경우로 나뉜다.

1. n-1개의 빌딩이 있을 때 왼쪽에서 보이는 빌딩 수가 l-1개, 오른쪽에서 보이는 빌딩 수가 r개인 경우에서 가장 왼쪽에 높이가 1인 빌딩을 세우는 경우 (n-1, l-1, r)
2. n-1개의 빌딩이 있을 때 왼쪽에서 보이는 빌딩 수가 l개, 오른쪽에서 보이는 빌딩 수가 r-1개인 경우에서 가장 오른쪽에 높이가 1인 빌딩을 세우는 경우 (n-1, l, r-1)
3. n-1개의 빌딩이 있을 때 왼쪽에서 보이는 빌딩 수가 l개, 오른쪽에서 보이는 빌딩 수가 r개인 경우에서 가장 양 끝을 제외한 빌딩 사이사이에 높이가 1인 빌딩을 세우는 경우 (n-1, l, r) * (n-2)

즉, dp[n][l][r] = dp[n-1][l-1][r] + dp[n-1][l][r-1] + dp[n-1][l][r] * (n-2)라는 것을 알 수 있다.

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

public class Main {
    static final int MOD = 1_000_000_007;
    static int[][][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()),
                L = Integer.parseInt(st.nextToken()),
                R = Integer.parseInt(st.nextToken());

        /**
         * dp의 첫 번째 인덱스는 빌딩의 개수 n을 의미
         * 두 번째 인덱스는 가장 왼쪽에서 봤을 때 보이는 빌딩의 수 l을 의미
         * 세 번째 인덱스는 가장 오른쪽에서 봤을 때 보이는 빌딩의 수 r
         * 예를 들면, dp[5][3][2]는 5개의 빌딩이 있을 때 왼쪽에서 3개, 오른쪽에서 2개가 보이는 경우의 수를 의미
         */
        dp = new int[N + 1][L + 1][R + 1];
        /**
         * n, l, r 중 하나라도 0인 경우는 존재하지 않으므로 0
         * 빌딩이 1개일 때는 l, r 모두 1인 경우만 오직 한 가지 존재하므로 dp[1][1][1] = 1로 초기화
         * 나머지는 검사하지 않았으므로 -1로 초기화
         */
        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] = -1;
        }

        System.out.println(search(N, L, R));
    }

    static int search(int n, int l, int r) {
        if(dp[n][l][r] != -1) return dp[n][l][r];

        long result = (long)search(n - 1, l, r) * (n - 2)
                + search(n - 1, l - 1, r)
                + search(n - 1, l, r - 1);

        return dp[n][l][r] = (int)(result % MOD);
    }
}