4-1 Pole

높이가 1, 2, ..., N 인 막대 N개가 일렬로 배치

막대를 왼쪽 혹은 오른쪽에서 보면,

큰 막대가 뒤에 있는 작은 막대를 가리게 됨

예를 들어 막대의 배치가 4, 1, 2, 3 순서로 되어 있음. 왼쪽에서 하나, 오른쪽에서 하나

막대의 개수 앤과 왼쪽에서 봤을 때 보이는 막대의 개수 L, 오른쪽에서 봤을 떄 보이는 막대의 갯수 R이 주어졌을 때

이러한 결과를 만드는 배치가 몇 가지가 가능한지 구하는 프로그램 작성

#include <stdio.h>

#define MAX_NUM 20

long long DP[MAX_NUM + 1][MAX_NUM + 1][MAX_NUM + 1];

int main(void)
{
    int T;
    int test_case;
    int N, L, R;

    freopen("text.txt", "r", stdin);
    scanf("%d", &T);

    DP[1][1][1] = 1;

    for (int n = 2; n <= MAX_NUM; n++)
    {
        for (int l = 1; l <= MAX_NUM; l++)
        {
            for (int r = 1; r <= MAX_NUM; r++)
            {
                DP[n][l][r] = DP[n - 1][l - 1][r] + (DP[n - 1][l][r] * (n - 2)) + DP[n - 1][l][r - 1];
            }
        }
    }

    for (test_case = 1; test_case <= T; test_case++)
    {
        scanf("%d %d %d", &N, &L, &R);

        long long ans = 0;
        ans = DP[N][L][R];
        printf("#%d %lld\n", test_case, ans);
    }

    return 0;
}

- 디피문제
- 수식을 어떻게 세워야 하는지
- 그리고 DP로 풀리는 문제 몇개를 볼 것