[BOJ] 고층 빌딩 - Compy's Blog

고층 빌딩

TimeLimit	MemoryLimit	Condition	TAG
2s	128MB	(1 ≤ N ≤ 100, 1 ≤ L, R ≤ N)	Math

오랜만에 수학 문제여서.. 약간? 고민의 시간을 가졌습니다. 최근에 그래도 문제를 풀면서 그냥 머릿속에서만 말고 블로그 쓰는김에 패드로 좀 끄적이고 있는데요.

제 의식의 흐름을 보여드리겠습니다.

이 방식으로

f(n,l,r)=f(n−1,l−1,r)+f(n−1,l,r−1)+(n−2)f(n−1,l,r)

이렇게 유도가 되더라구요. 그렇게 그냥 코드를 작성하면 됩니다.

정답 코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <iomanip>
#include <string>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
#include <climits>
using namespace std;
using ll = unsigned long long;
ll MOD = 1'000'000'007;
//ll MOD = 1.8446744074E19;

int N, L, R;

ll dp[101][101][101];

ll solution(ll n, ll l, ll r){
    ll result = 0;
    if (l <= 0 || r <= 0 || l + r > n + 1) return 0;
    if(n == 1) return (l == 1 && r == 1);
    
    if(dp[n][l][r] != -1) return dp[n][l][r];
    
    // solution(n+1, r, l) = solution(n, r-1, l) + solution(n, r, l-1) + solution(n, r, l) * n
    result = ((solution(n-1, l, r-1)%MOD + solution(n-1, l-1, r)%MOD)%MOD + (solution(n-1, l, r) * (n-2))%MOD)%MOD;
    dp[n][l][r] = result;
    return result;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> L >> R;
    
    for(int i = 0; i < 101; i++){
        for(int j = 0; j < 101; j++){
            
            for(int k = 0; k < 101; k++){
                dp[i][j][k] = -1;
            }
        }
    }
    
    
    cout << solution(N, L, R);
    
    return 0;
}