🍋 문제링크

1010번: 다리 놓기

🍎 코드 제출 기록 (메모리 및 시간)

메모리 : 1120 KB

시간 : 0 ms

🍉 Code

#include <stdio.h>

int dp[30][30];
int ft_dp(int n, int m);
int main()
{
    int t, n, m;
    scanf("%d", &t);

    for(int i = 0;i<30;i++)
        for(int j=0;j<30;j++)
            dp[i][j]=0;
    
    for(int i = 0 ; i < 30 ; i++){
        dp[i][i] = 1;
        dp[i][0] = 1;
    }
    while(t--)
    {
        scanf("%d %d", &n, &m);
        printf("%d\\n", ft_dp(n,m));
    }
    return (0);
}

int ft_dp(int n, int m)
{
    if(dp[m][n] == 0)
        dp[m][n] = ft_dp(n, m-1) + ft_dp(n-1, m-1);
    return (dp[m][n]);
}

🥝 메모

<공식>

 $mCn = m-1Cn + m-1Cn-1$

<초기화 부분>

for(int i = 0;i<30;i++)
        for(int j=0;j<30;j++)
            dp[i][j]=0;
    
for(int i = 0 ; i < 30 ; i++){
    dp[i][i] = 1;
    dp[i][0] = 1;
}