1010번

1010번 - 다리놓기

D[n][m] = 왼쪽n개,오른쪽m개 있을 때 놓을 수 있는 다리의 경우

라는 점화식을 세워서 문제를 풀었다.

기저 조건으로는 

- 왼쪽에 세울 다리가 남았는데, 오른쪽 다리가 부족한 경우 return 0

- 왼쪽에 세울 다리가 없을 때, return 1;

for문을 통해서 왼쪽과 오른쪽을 연결하는데, 오른쪽으 가장 위쪽부터 아래로 내려가게끔 연결시켰다.

풀고 다른 분들을 보니 그냥 조합의 갯수를 구해서 바로 푸셨다..

<정답 코드>

#include<iostream>
#include<string.h>
using namespace std;
int D[31][31];
int go(int n,int m)
{
    if (n > 0 && m <= 0)
    {
        return 0;
    }
    if (n == 0 && m >= 0)
    {
        return 1;
    }
 
    if (D[n][m] >= 0)
    {
        return D[n][m];
    }
 
    if (D[n][m] == -1)
    {
        D[n][m] = 0;
    }
 
    for (int i = m; i >=1; i--)
    {
        D[n][m] += go(n - 1, i-1);
    }
    
    return D[n][m];
 
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "r", stdin);
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        memset(D, -1, sizeof(D));
        int n, m;
        cin >> n >> m;
        
        cout << go(n, m) << "\n";
 
        
    }
 
    return 0;
}