백준 1328 고층 빌딩

 

 

이 문제는 빌딩을 세워놓고 왼쪽에서 봤을 때 보이는 개수와 오른쪽에서 보이는 개수가 주어진 경우 이를 만족하는 빌딩의 조합이 몇개 있는지 찾는 문제입니다.

 

높이가 제일 높은거부터 세우고 차례대로 하나씩 세우는 식으로 처음에 생각을 했는데 뭔가 잘 안떠올라서 힌트를 조금 보고 해결했습니다. 

 

결론적으로 높이가 N인 빌딩 까지 세우고 그다음 높이가 N-1인 빌딩을 세운다고 하면 3가지의 경우로 나눌 수 있습니다.

 

1. 가장 왼쪽에 세우는 경우

2. 가장 오른쪽에 세우는 경우

3. 현재 있는 빌딩들 사이에 세우는 경우

 

1번의 경우 왼쪽에서 바라보는 개수가 하나 증가합니다.

2번의 경우 오른쪽에서 바라보는 개수가 하나 증가합니다.

3번의 경우 개수의 변화가 없습니다. (N-1 은 현재 가장 작은 빌딩이므로)

 

1,2번의 경우는 한가지만 존재하지만 3번의 경우는 N개의 빌딩이 있다면 N-2개만큼의 사이 공간이 존재하므로 N-2만큼 값을 곱해주어야 함을 알 수 있습니다.

이런식으로 생각하여 Top-down DP를 이용하여 해결하면 되겠습니다.

 

dp식의 정의는 다음과 같습니다.

 

dp[i][j][k]  ->  i개의 건물 이 있을때 왼쪽에서 보면 j개 오른쪽에서 보면 k개가 존재하는 경우의 수

 

코드는 다음과 같습니다.

 

#include <bits/stdc++.h>

using namespace std;
#define MOD 1000000007

long long dp[110][110][110]; // dp[i][j][k] i개의 건물 이 있을때 왼쪽에서 보면 j개 오른 k개
int N, L, R;

long long sol(int cur, int l, int r){

    if(cur == 1) {
        if(l == L && r == R) return 1;
        else return 0;
    }

    long long &ret = dp[cur][l][r];
    if(ret != -1) return ret;

    ret = sol(cur-1, l+1, r)%MOD + sol(cur-1, l, r+1)%MOD + (cur-2)*sol(cur-1, l ,r)%MOD;
    ret %= MOD;

    return ret;
}

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    cin >> N >> L >> R;
    memset(dp, -1, sizeof(dp));
    cout<<sol(N, 1, 1); //N번째 빌딩부터 하나씩 추가함

    return 0;
}