[백준 1010] 다리 놓기

0. 제목

• 백준 1010 다리 놓기
• BOJ 1010 다리 놓기
• C++ 1010 다리 놓기

---

1. 문제

https://www.acmicpc.net/problem/1010

---

2. 풀이

• mCn을 묻는 문제이다.
• dp방식을 이용하여 값을 저장해놓는다.
• dp[i][j]의 값은 왼쪽에 i개, 오른쪽에 j개가 있을 때 연결 방법의 개수이다.
• 왼쪽에 3개, 오른쪽에 5개가 있다고 가정해보자.
• 왼쪽의 가장 위에 것이 오른쪽 가장 위로 가면 나올 수 있는 방법 수는 dp[i-1][j-1] 이 된다.
• 왼쪽의 가장 위에 것이 오른쪽 두번 째로 가면 나올 수 있는 방법 수는 dp[i-1][j-2] 이 된다.
• 이렇게 쭉 반복하면 2차원 인덱스의 값은 j-1, j-2, ..., i-1 가 가능하다.
• 점화식을 써보면 다음과 같다.
• dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] + dp[i-1][j-3] + ... + dp[i-1][i-1]
• 위 점화식을 반복문을 이용하고 매 테스트 케이스마다 dp를 초기화 시켜주면 된다.

---

3. 코드

#include <iostream>
#include <cstring>
using namespace std;
 
int main(int argc, const char * argv[]) {
    int T, N, M;
    int dp[31][31];
    
    cin >> T;
    for(int i = 0; i < T; i++){
        cin >> N >> M;
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= M; i++){
            dp[1][i] = i;
        }
        
        for(int i = 2; i <= N; i++)
            for(int j = i; j <= M; j++)
                for(int k = j-1; k >= i-1; k--)
                    dp[i][j] += dp[i-1][k];
        
        cout << dp[N][M] << '\n';
    }
    
    return 0;
}