백준 8895 - 막대 배치

문제

www.acmicpc.net/problem/8895

8895번: 막대 배치

 

 

풀이

 

다음과 같은 점화식을 만든다. dp[n][l][r] = n개의 막대가 있을 때, 왼쪽에서 l개 오른쪽에서 r개 막대가 보인다.

그리고 길이 1인 막대가 왼쪽에 있을 때, 오른쪽에 있을 때, 가운데 있을 때로 나누어서 생각해 본다.

 

1. 길이 1인 막대가 왼쪽에 있을 때 : 이 막대가 사라졌을 때 왼쪽에서 보이는 막대가 1개 사라지므로

점화식은 다음과 같다.

dp[n-1][l-1][r]

 

2. 길이 1인 막대가 오른쪽에 있을 때 : 이 막대가 사라졌을 때 오른쪽에서 보이는 막대가 1개 사라지므로

점화식은 다음과 같다.

dp[n-1][l][r-1]

 

3. 길이 1인 막대가 가운데에 있을 때 : 이 막대가 사라져도 왼쪽이나 오른쪽에서 보이는 막대의 개수가 사라지지 않는다.

따라서 점화식은 다음과 같다.

dp[n-1][l][r]

이 때, 길이 1인 막대가 가운데에 있는 경우는 n-2 개가 된다.

 

따라서 점화식은 다음과 같이 만들어진다.

dp[n][l][r] = dp[n-1][l-1][r] + dp[n-1][l][r-1] + (n-2) * dp[n-1][l][r]

 

 

코드

 

#include <bits/stdc++.h>
 
using namespace std;
 
// n개의 막대, 왼쪽에서 보이는 막대, 오른쪽에서 보이는 막대
// dp[n][l][r]
long long dp[21][21][21];
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    int t;
    int n, l, r;
 
    cin >> t;
    dp[1][1][1] = 1;
 
    for (int i=2; i<=20; i++) {
        for (int j=1; j<=20; j++) {
            for (int k=1; k<=20; k++) {
                dp[i][j][k] = dp[i-1][j-1][k] + dp[i-1][j][k-1] + (i-2)*dp[i-1][j][k];
            }
        }
    }
 
    while (t--)
    {
        cin >> n >> l >> r;
        cout << dp[n][l][r] << '\n';
    }
 
 
    return 0;
}