(C/C++) 백준 1010번 - 다리 놓기

문제출처: https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

1. 코드

#include <iostream>
#include <algorithm>
 
using namespace std;
int test;
int n, m;
int dp[31][31];
 
//조합 공식
//mCn = m-1Cn+m-1Cn-1
int find(int n, int m) {
    if (dp[m][n] == 0)
        dp[m][n] = find(n, m - 1) + find(n - 1, m - 1);
    return (dp[m][n]); 
}
 
int main() {
    
    scanf("%d", &test);
 
    //test 케이스 별로 배열 초기화 해주기
    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;
    }
 
    for (int i = 0; i < test; i++) {
        scanf("%d %d", &n, &m);
        printf("%d\n", find(n, m));
    }
    return 0;
}

2. 해결과정

M개에서 N개를 겹치지 않게 뽑는 조합의 문제  mCn을 풀어주면 된다.

점화식은 m-1Cn-1+m-1Cn 성질과 nCn=1, nC0=1를 이용해주면 된다.

테스트 케이스 별로 배열을 초기화 시켜줘야한다.

 

3. 느낀점

처음에는 초기화를 안시켰고, 조합을 구현하는것에 어려움을 느꼈다. dp는 어려워잉