[BOJ] 1010_다리 놓기

다리 놓기

 

문제 링크: https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

왼쪽에 있는 지점에서 오른쪽에 있는 지점으로 선긋기 이나, 겹치면 안된다.

여기까지 이해한다면 다음과 같이 이해할 수 있다.

• 서쪽의 임의의 점을 동쪽의 임의의 점으로 이었을 때 나머지 지점은 저절로 지정된다.

먼저, a(n, m)을 정의하겠다.
a(n, m): 서쪽의 남은 점의 개수 n과 동쪽의 남은 점의 개수 m에 대하여 놓을 수 있는 다리의 수.
위 이미지에 따르면 a(4, 6)이라 할 수 있다.

나는 임의의 점을 서쪽의 지점 가장 첫번째 점을 기준으로 생각해보았다.

각 첫번째 지점을 이었을 때 나머지 지점에 대하여 a(3, 5)가 된다.

다음으로 서쪽의 첫번째 지점과 동쪽의 두 번째 지점을 잇는다면 다음과 같다.

나머지 지점에 대하여 a(3, 4)가 된다.

다음으로 서쪽의 첫번째 지점과 동쪽의 세 번째 지점을 잇는다면 다음과 같다.

나머지 지점에 대하여 a(3, 3)가 된다.
하지만 이때, 같은 개수에 대하여 가능한 경우의 수는 1가지 밖에 없다.
서로 겹치면 안되므로 다음과 같은 경우만 가능하다.

이를 통해 a(n, m)에 대하여 n == m일 경우 1임을 알 수 있다.
따라서, a(4, 6) = a(3, 5) + a(3, 4) + a(3, 3)의 식을 세울 수있다.
같은 방식으로 a(3, 5), a(3, 4) 의 식을 세울 수 있다.
a(3, 5) = a(2, 4) + a(2, 3) + a(2, 2)
a(3, 4) = a(2, 3) + a(2, 2)
...

위 식을 통해 다음과 같은 규칙을 알 수 있다.

• a(n, m) = a(n-1, m-1) + a(n-1, m-2) + ... + a(n-1, n-1)
• 단, a(x, x) = 1 (x는 임의의 정수)

이 식을 이용하여 재귀함수를 만들어보자.

int recursive(int n, int m) {
    if (n == m)
        return 1;
    else {
        int count = 0;
        for (int i = m-1; i >= n-1; i--) {
            count += recursive(n-1, i);
        }
        return count;
    }
}

문제를 통해 한 가지 조건을 더 붙일 수 있다.

• n == 1일 경우 이때 가능한 경우의 수는 m개 이다.

이를 추가하여 전체 코드를 보자.

정답 코드

#include<iostream>
using namespace std;

int recursive(int n, int m) {
    if (n == m)
        return 1;
    else if (n == 1)
        return m;
    else {
        int count = 0;
        for (int i = m-1; i >= n-1; i--) {
            count += recursive(n-1, i);
        }
        return count;
    }
}


int main() {

    int T;
    cin >> T;
    while (T--) {
        int N, M;
        cin >> N >> M;
        cout << recursive(N, M) << endl;
    }

    return 0;
}