[ 백준 1010 ] 다리놓기 (C++)

백준의 다리놓기(1010) 문제이다.

( 문제 바로가기 )

[ 문제설명 ]

- 큰 강을 기준으로 강의 서쪽과 동쪽에 다리를 지을 수 있는 사이트가 있다. 입력으로 서쪽 사이트의 갯수와, 동쪽 사이트의

  갯수가 주어진다.

- 이 때, 만들 수 있는 다리의 총 경우의수를 구하는 것이 문제인데, 이 때 다리는 서로 겹칠 수 없고, 이미 선택된 사이트에

  또 다른 다리가 생성될 수 없다는 조건이 있다.

[ 문제풀이 ]

1. 먼저 가장 간단한 경우부터 생각을 해보자. 서쪽 사이트에서 동쪽 사이트로 다리를 만들어야 하는데, 서쪽 사이트의

   갯수가 1개이고 동쪽 사이트의 갯수가 A개라고 생각을 해보자.

   즉, 서쪽에는 점이 하나 있고, 동쪽에는 점이 A개가 있다. 이 때, 나올 수 있는 경우의수는 ???

   A개이다.

 

   그럼 여기서 위에서 말한 내용을 식으로 표현해보자.

   나는 이 부분을 위해서 DP[][] 라는 2차원 배열을 사용했으며 이 배열의 의미는

   DP[A][B] = "서쪽 사이트가 A개이고, 동쪽 사이트가 B개 일 때 나올 수 있는 경우의 수" 를 의미한다.

   그럼 위에서 말한 내용을 식에 대입해보면 DP[1][1] = 1 , DP[1][2] = 2 , .... , DP[1][M] = M 이 될것이다.

 

   그럼 이번에는 서쪽 사이트가 2개이고, 동쪽 사이트가 A개일 때를 생각해보자. (A = 3 이라고 가정)

  

    그림으로 표현하면 이렇게 될 것이다. (1)번 그림처럼, 서쪽 사이트의 1번 사이트가, 동쪽 사이트의 1번 사이트를 선택

    하는 경우, A-1개 즉, 2개의 경우의 수가 생기며, 2번 사이트를 선택하는 경우, 1개의 경우의 수가 생기게 된다.

    여기서 (1)번 그림에서 주황색으로 연결되어있는 3개의 사이트에 주목해보자. 주황색으로 연결되어 있는 그림만

    본다면, 1개의 사이트에서 2개의 사이트를 연결하는 경우의 수가 된다. 즉 DP[1][2] = 2 가 된다.

    (2)번 그림에서는 DP[1][1]의 식이 그림으로 표현되고 있다.

    그럼 정리해서 식으로 한번 적어보자.

    DP[2][3] = DP[1][2] + DP[1][1] 이 된다. 이를 이해하기 쉽게 말로 풀어서 써보자면

    "서쪽에 2개의 사이트가 있고, 동쪽에 3개의 사이트가 있을 때 만들 수 있는 다리의 경우의 수는

     서쪽에 1개의 사이트가 있고 동쪽에 2개의 사이트가 있을 때 만들 수 있는 다리의 경우의 수 +

     서쪽에 1개의 사이트가 있고 동쪽에 1개의 사이트가 있을 때 만들 수 있는 다리의 경우의 수 입니다." 가 된다.

 

    결과적으로 이 식을 통해서 도출해 낼수 있는 점화식은

    DP[A][B] = DP[A-1][B-1] + DP[A-1][B-2] + ... 이렇게 될 것이다.

    이 식을 반복문 안에서 식으로 표현하기도 조금 헷갈렸는데, 정확한 식은 소스코드를 참고해 보도록 하자 !

[ 소스코드 ]

#include<iostream>
#include<cstring>
 
#define endl "\n"
#define MAX 30 + 1
using namespace std;
 
int N, M;
int DP[MAX][MAX];
 
void Initialize()
{
    memset(DP, 0, sizeof(DP));
}
 
void Input()
{
    cin >> N >> M;
}
 
void Solution()
{
    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; k >= i; k--)
            {
                DP[i][j] = DP[i][j] + DP[i - 1][k - 1];
            }
        }
    }
 
    cout << DP[N][M] << endl;
}
 
void Solve()
{
    int Tc;
    cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}