[BOJ] 1328 고층 빌딩

문제

1328번: 고층 빌딩

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

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

풀이

코드

#include <cstdio>
#include <cstring>
#define MOD 1000000007
using namespace std;
typedef long long ll;
 
int n, l, r;
ll dp[100][100][100];
 
ll go(int ix, int le, int ri) {
    if (ix == n) {
        if (le == l and ri == r) return 1;
        return 0;
    }
    if (dp[ix][le][ri] != -1) return dp[ix][le][ri];
    ll ret = 0;
    if (ix >= 2) ret = go(ix+1, le, ri) * (ix-1) % MOD;
    ret += go(ix+1, le+1, ri) % MOD + go(ix+1, le, ri+1) % MOD;
    return dp[ix][le][ri] = ret % MOD;
}
 
int main() {
    memset(dp, -1, sizeof(dp));
    scanf("%d %d %d", &n, &l, &r);
    printf("%lld", go(1, 1, 1));
}