[백준 8895] 막대 배치

문제

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

 

알고리즘

DP

 

풀이

서로 다른 $N$개의 막대를 좌우로 쌓을 때, 옆에서 보이는 l, r의 경우의 수를 구하는 문제입니다.

 

$cache[n][l][r]$을 선언하여 풀되, 다음 상태(n+1)를 갱신할 때는 기존 막대의 크기를 1씩 키우고 가장 작은 막대(높이 1)를 추가하는 것으로 생각하여 풀면 쉽게 풀 수 있습니다. 막대를 가장 왼쪽, 오른쪽에 배치하는 것은 직관적이나 막대를 막대들 사이에 넣을 때 가장 작은 막대를 추가한다면 기존 상태 $cache[n][l][r]$에서 $cache[n+1][l][r]$ 만 갱신하기 때문에 신경쓸 것이 적어집니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

#define int long long

int T, n, l, r;
int cache[21][21][21];

signed main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> T;
    cache[1][1][1] = 1;
    for (int i = 1; i <= 19; ++i) {
        for (int j = 1; j <= 19; ++j) {
            for (int k = 1; k <= 19; ++k) {
                cache[i + 1][j + 1][k] += cache[i][j][k];
                cache[i + 1][j][k + 1] += cache[i][j][k];
                cache[i + 1][j][k] += (i - 1) * cache[i][j][k];
            }
        }
    }

    while (T--) {
        cin >> n >> l >> r;
        cout << cache[n][l][r] << '\n';
    }
    return 0;
}