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

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

[ 문제 바로가기 ]

[ 문제풀이 ]

먼저 간단한 상황들을 통해서 문제 해결방법에 접근해보자.

지금부터는 간략한 표현을 위해서 F[A][B] = C 라는 수식을 이용해서 표현해보자.

F[A][B] = C 의 의미는 "강 왼쪽에 A개의 사이트가 있고 , 강 오른쪽에 B개의 사이트가 있을 때, 다리를 지을 수 있는 경우의 수는 총 C개입니다." 를 의미한다.

또한, 강의 왼쪽에도 , 오른쪽에도 사이트들이 존재하는데 편하게 표시하기 위해서 위에서 부터 1번 ~ N번, 1번 ~ M번 사이트로 표현하겠다.

# Case1 : 왼쪽에 1개의 사이트가 존재하는 Case.

오른쪽에 사이트의 갯수가 M개라고 가정하면, 이 경우 발생 가능한 경우의 수는 M개이다.

왜냐하면 왼쪽에는 1개의 사이트만 존재하고 , 이 1개의 사이트와 연결 가능한 사이트가 M개 이기 때문에 최종적으로 발생 가능한 경우의 수는 M개이다.

F[1][M] = M.

# Case2 : 왼쪽에 2개의 사이트가 있고 오른쪽에 2개의 사이트가 존재하는 Case.

.

경우의 수가 몇가지가 있을까 ?? 딱 봐도 1가지 이다. 서로 마주보고 있는 사이트들끼리 연결하는 방법 1가지 밖에 존재하지 않는다. 즉 ! 왼쪽에 존재하는 사이트의 수와 오른쪽에 존재하는 사이트의 수가 같다면, 다리를 놓을 수 있는 경우의 수는 1가지 이다.

F[A][A] = 1

# Case3 : 왼쪽에 2개의 사이트가 있고 오른쪽에 3개의 사이트가 존재하는 Case.

.

발생 가능한 경우를 모두 만들어 보면 다음과 같은 경우들이 있다.

.

위의 그림과 같이 3가지 경우가 발생한다. 그럼 지금 이야기 한 Case3의 경우의 수를 앞써 이야기한 Case1과 Case2를 통해서 한번 계산을 해보자.

먼저 발생할 수 있는 3가지 경우 중, 다음 2가지 경우를 주목해보자.

.

이렇게 2가지 경우는 한 가지 공통점이 있다. 바로 왼쪽에 있는 1번 사이트를 오른쪽에 있는 1번 사이트로 연결 시켰다는 것이다.

.

위의 그림에서 표시된 파랑색 다리를 공통적으로 갖는다는 것이다.

그럼 ! 저 파랑선분을 하나의 '고정된 다리' 라고 생각해보자.

그럼 왼쪽에 있는 2번 사이트에서는 선택권이 생기게 된다.

.

위의 그림과 같이 2번 사이트에서는 2개의 사이트 중에서 하나를 고를 수 있는 선택권이 생기게 되는 것이다.

파랑색 다리는 고정된 다리니까, 나머지 사이트들만 본다면, 위의 상황은 "왼쪽에 1개의 사이트가 존재하고 , 오른쪽에 2개의 사이트가 존재할 때, 다리를 놓을 수 있는 경우의 수" 를 구하는 상황과 같아진다.

우리는 이 부분을 이미 구해놨다. 바로 Case1 에서 !

왼쪽에 1개의 사이트가 있고, 오른쪽에 M개의 사이트가 있다면 이 때 다리를 놓을 수 있는 경우의 수는 M 가지라고 했다.

Case1에 의하면 위의 상황에서는 오른쪽에 2개의 사이트가 존재하므로 발생 가능한 다리를 놓는 경우의 수는 2가지가 생기게 되는 것이다.

"F[2][3]의 값을 구하기 위해서 F[1][2] 를 사용 !"

그럼 이 경우를 한번 보자.

.

이 경우에서는 왼쪽 1번 사이트가 오른쪽 1번 사이트가 아닌 2번 사이트와 연결되어 있다. 마찬가지로 이 다리를 고정된 다리라고 가정해보자.

.

이렇게 보면 왼쪽 2번 사이트 입장에서는 선택권이 없다. 왜냐하면 연결할 수 있는 사이트가 1개 뿐이기 때문이다.

우리는 이 부분도 이미 계산을 해놨다. Case2 에서 ! 바로 "왼쪽에 존재하는 사이트의 수 = 오른쪽의 존재하는 사이트의 수 일 때, 발생 가능한 경우의 수는 1개이다." 라고 이미 계산을 해놨다.

F[2][3]을 구하기 위해서 F[1][1]을 사용 !

그럼 위의 내용을 수식으로 표현해보면 F[2][3] = F[1][2] + F[1][1] 이 된다. 이 부분 만으로는 일반화된 식을 찾기 힘드니까 한 가지 예시만 더 들어보자.

.

위의 상황을 계산해보자. F[2][3]을 구할 때 처럼, 왼쪽 1번 사이트와 연결된 어떤 사이트의 다리를 고정된 다리라고 가정해보면서 해결해보자.

.

가장 첫 번째로 위와 같이 고정된 다리를 설치했다고 가정해보자.

그럼 발생 가능한 경우의 수는 ??

왼쪽에 2개의 사이트가 있고 오른쪽에 3개의 사이트가 남아있는 형태이기 때문에 F[2][3] 이 된다. 이 또한 위에서 구해놓은 값이다.

.

두 번째로 위와 같이 다리를 고정시켜 놨다고 가정해보자.

그럼 발생 가능한 경우의 수는 왼쪽에 2개의 사이트, 오른쪽에 2개의 사이트가 남아있는 형태이기 때문에 F[2][2]가 되고, 왼쪽 사이트의 수와 오른쪽 사이트의 수가 같기 때문에 이 때는 1가지 이다.

세 번째 상황부터는 다리를 연결할 수 없게 된다. 왜냐하면 왼쪽 1번 사이트와 오른쪽 3~4번 사이트 중 하나가 연결되는 꼴인데, 그렇게 되면 문제에서 제시한 조건대로 다리를 놓을 수가 없게 된다.

정리해보면 F[3][4] = F[2][3] + F[2][2] 로 계산을 하였다.

그럼 위에서 계산한 F[2][3]과 F[3][4]를 통해서 일반화된 식을 한번 찾아보자.

F[2][3] = F[1][2] + F[1][1]

F[3][4] = F[2][3] + F[2][2]

왼쪽에 N개의 사이트가 있다면, F[N][?] = F[N - 1][?] + F[N - 1][?] 의 형태로 나올 것이다.

왜냐하면 ! 위에서 풀었듯이, 우리는 "왼쪽에 있는 1번 사이트를 무조건 고정된 다리로 설치해놓고, 나머지 N - 1개의 사이트들을 연결하는 경우의 수를 구했기 때문" 이다. 그러므로 F[N - 1][?] + F[N - 1][?] 의 형태가 된다.

그럼 뒤에 ? 에는 무슨 값들이 들어갈까 ?? 물음표에는 "오른쪽에 남아있는 사이트의 갯수" 가 된다.

오른쪽에 사이트의 갯수가 M개 였다면 , 왼쪽 1번 사이트와 고정된 다리로 연결된 사이트 1개를 제외하게 되면 결국 M - 1개를 연결하는 형태가 될 것이고, 그 고정된 다리가 오른쪽 사이트 1번에서 2번, 3번, 4번... 순으로 점차 증가할 때 마다, 남은 N - 1개의 사이트에서 선택할 수 있는 다리의 갯수는 점차 감소하게 된다.

따라서 하나의 일반화된 식을 나타내면

F[N][M] = F[N - 1][M - 1] + F[N - 1][M - 2] + ...+ F[N - 1][N - 1] 이 된다.

이를 점화식으로 코드를 구현해 주었다.

3중 for문으로 이를 표현해 주었고, 3개의 포문은 각각 왼쪽 사이트 1 ~ N , 오른쪽 사이트 1 ~ M , 고정된 다리를 제외한 남은 오른쪽 사이트의 갯수로 표현해 주었다.

[ 소스코드 ]

#include <iostream>
#include <cstring>
 
#define endl "\n"
#define MAX 40
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;
}