Compy's Blog
249 words
1 minutes
[BOJ] 막대 배치
2025-10-05

막대 배치

TimeLimitMemoryLimitConditionTAG
1s256MB(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;
}

[BOJ] 막대 배치
https://compy07.github.io/Blog/posts/boj/8895/
Author
뒹굴뒹굴 이정훈 공부방
Published at
2025-10-05