[BOJ 1328] 고층 빌딩

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

 이 또한 DP문제이다. N,L,R 이 주어졌을때 볼수 있는 가지수를 출력하는 문제이다. DP 테이블의 정의는 DP[i][j][k] = 빌딩이 i개 있을때 왼쪽으로 j개, 오른쪽으로 k개 가 보일때의 개수 라고 정의하고 문제를 접근할 수 있다.  

 해당 문제를 풀때 힌트라고 한다면 문제를 접근할때 2~n까지의 빌딩이 세워져 있다고 가정을 하고 높이 1의 건물을 넣을 수 있는 경우로 문제를 접근하면 좀 더 쉽게 풀 수 있다. 

 만약 높이기 1인 빌딩이 가장 왼쪽에 배열되게 된다면 dp[i][j][k] +=dp[i-1][j-1][k] 가 될것이고, 가장 오른쪽에 배열된다면 dp[i][j][k] += dp[i-1][j][k-1] 으로 생각할 수 있다. 또한 이 두 경우를 제외하고는 1이 어느 곳에 배치가 되어도 l,r에는 변화를 줄 수 없기 떄문에 dp[i][j][k] += dp[i-1][j][k] * (n-2) 의 값을 넣어줄 수 있다. (여기서 n-2를 곱해주는 이유는 왼쪽, 오른쪽 배열하는 경우를 제외하고는 전부다 그 값을 그대로 가져오기 때문이다. )

 

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <set>
#include <queue>
#include <stack>
#define MAX_N 100
#define INF 1e8
#define MOD 1000000007
 
typedef long long ll;
using namespace std;
 
ll n,r,l,dp[MAX_N+1][MAX_N+1][MAX_N+1];
 
int main(){
    ios:: sync_with_stdio(false);
    cin.tie(0);
    
    memset(dp,0,sizeof(dp));
    cin >> n >> l >>r;
    
    dp[1][1][1] = 1;
    
    for(int i=2;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                dp[i][j][k] = dp[i-1][j-1][k]+ dp[i-1][j][k-1] + dp[i-1][j][k]*(i-2);
                dp[i][j][k] %=MOD;
            }
        }
    }
    
    cout <<dp[n][l][r] %MOD<<endl;
    return 0;
}