1328번

1328번 - 고층 빌딩

점화식 D[N][L][R] = N개의 건물을 봤을 때 왼쪽에서 L개 오른쪽에서 R개인 경우의 수

사실 점화식을 세웠지만, 이 식을 다른 N,L,R 과 연관시키는게 사실 너무 어려웠다.

나도 결국 다른 사람들의 풀이에서 힌트를 얻고 문제를 풀 수 있었다. (다시 풀어봐야겠다)

이 문제는 결국 높이 1의 빌딩을 어느 곳에 놓을 것인가 하는 문제로 끝이난다.

어떻게 다른 사람들은 이걸 생각했는지 참 신기하다...

높이 1의 건물을 맨 왼쪽에 뒀을 때, 맨 오른쪽에 뒀을 때, 그리고 나머지 부분에 뒀을 때로 나뉘게 된다.

가장 작은 건물이기 때문에 맨 왼쪽에 두면 N 과 L 이 1씩 증가.

맨 오른쪽에 두면 N과 R이 1씩 증가.

나머지 부분에 두면 N은 증가하지만 L과 R은 변화가 없다.

따라서 이를 통해 다른 N,L,R 과 D[N][L][R] 을 연결하는 식이 생긴다.

D[N][L][R] = D[N-1][L-1][R] + D[N-1][L][R-1] + D[N-1][L][R] * (N-2) 

                (맨 왼쪽 둘때)    (맨 오른쪽 둘때)   (나머지에 둘 때 경우의 수는 N-2가 된다)

그리고 재귀로 풀 때 초기값은 우선 N=1 일때 L,R은 무조건 1이어야 한다. (조건 1)

그리고 N,L,R 은 무조건 1보다 작으면 안된다.. (조건 2)

그 다음 중요한것은 long long 형을 써야 한다는 사실! 빼먹으면 안된다.

<정답 코드>

#include<iostream>
#include<string.h>
 
using namespace std;
const int mod = 1000000007;
long long D[101][101][101];
long long go(int n, int l, int r)
{
    if (n < 1 || l < 1 || r < 1)
    {
        return 0;
    }
    if (n == 1)
    {
        if (l == 1 && r == 1)
        {
            return 1;
        }
        else
        {
            return 0;
        }
        
    }
    if (D[n][l][r] >= 0)
    {
        return D[n][l][r];
    }
    if (D[n][l][r] == -1)
    {
        D[n][l][r] = 0;
    }
 
    D[n][l][r] = (go(n - 1, l - 1, r)%mod + go(n - 1, l, r - 1)%mod + (go(n - 1, l, r)*(n - 2))%mod);
 
    return D[n][l][r] %mod;
}
int main()
{
    int N, L, R;
    scanf("%d %d %d", &N, &L, &R);
    memset(D, -1, sizeof(D));
    printf("%lld\n", go(N, L, R));
 
    return 0;
}