[백준] 1328번 고층 빌딩

문제 링크: https://www.acmicpc.net/problem/1328

문제 및 입출력

문제 접근

도저히 생각이 나지 않아 다른 사람의 블로그를 참고를 하였다.

이전의 빌딩 갯수에서 빌딩의 높이를 하나씩 높인다고 가정한다. 그 후에, 높이가 1인 빌딩을 놓을 곳을 찾으면 된다. 가장 좌측에 놓는 경우와 가장 우측에 놓는 경우는 각각 왼쪽에서 보이는 경우, 오른쪽에서 보이는 경우가 1씩 추가된다.
양 끝이 아닌 부분들은 보이는 갯수에 대한 변화는 없기 때문에 놓을 수 있는 위치는 i-2이다.

점화식: dp[i][j][k] = cache[i-1][j-1][k] + cache[i][j][k-1] + cache[i-1][j][k] * (i-2)

코드 구현(c++)

#include<iostream>

using namespace std;

typedef long long ll;
ll mod = 1e9 + 7;
ll cache[102][102][102];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int N, L, R;
    cin >> N >> L >> R;
    
    cache[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++){
                cache[i][j][k] = (cache[i-1][j-1][k] + cache[i-1][j][k-1] + cache[i-1][j][k] * (i-2)) % mod;
            }
        }
    }
    cout << cache[N][L][R] << "\n";
}