다리놓기 | 백준 1010번

#include<cstdio>
int main(void)
{
    int n, m, t;
    int val[30][30]={0};
    
    scanf("%d", &t);
    
    for(int test=0; test<t; test++)
    {
        scanf("%d%d", &n, &m);
        for(int j=0; j<m; j++)
        {
            val[0][j] = j+1;
        }
        for(int i=1; i<n; i++)
        {
            for(int j=i; j<m; j++)
            {
                val[i][j] = val[i][j-1] + val[i-1][j-1];
            }
        }
        
        printf("%d\n", val[n-1][m-1]);
    }
    return 0;
}

이런저런 생각을 하다가 엉뚱한데 시간을 보냈지만, 그림을 그려보면 왼쪽에 i개 오른쪽에 j개가 있을 때의 경우의 수는, 왼쪽 i, 오른쪽에 j-1개 있을 때와 왼쪽에 i-1개 오른쪽에 j-1개 있을 때의 합과 같다.

오른쪽이 하나 적었을 경우와, 오른쪽이 추가 되었을 때, 왼쪽의 가장 큰 것이 오른쪽을 포함하는 경우를 더하면 된다.

알고리즘 분류 : 다이나믹 프로그래밍

• Twitter
• Facebook
• Google
• Tumblr
• Pinterest