249 words
1 minutes
[BOJ] 막대 배치
TimeLimit | MemoryLimit | Condition | TAG |
---|---|---|---|
1s | 256MB | (1 ≤ N ≤ 20, 1 ≤ L, R ≤ N) | Math |
솔직히 날먹이었따!
고층 빌딩 이거 재탕 문제여서 그냥 거의 바로 풀었던거 같아요.
정답 코드
#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);
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;
}
}
}
int T;
cin >> T;
while(T --> 0){
cin >> N >> L >> R;
cout << solution(N, L, R) << "\n";
}
return 0;
}