[C++백준 1010:다리 놓기]

[문제 링크]

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

1010번: 다리 놓기

문제

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

 

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

출력

각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.

해석

 - 왼쪽에는 N개, 오른쪽에는 M개의 사이트(다리를 놓을 수 있는 곳) 존재

 - 하나의 사이트에 두 개의 다리를 놓을 수 없음

 - 두 개의 다리가 겹치게 놓을 수 없음

 

코드

[1] 

문제를 처음 봤을 때 생각난 해결 방법은 팩토리얼을 이용하는 방법이었다.

M!/N!*(M-N)! 을 해도 결과는 나오지만 자료형에서 오버플로우가 발생했다.

#include <iostream>
using namespace std;
 
double factorial(int n) {
    if (n == 0) {
        return 1;
    }
    double res = n * factorial(n - 1);
    return res;
}
 
int main() {
    int T, N, M;
    cin >> T;
    
    while (T--) {
        cin >> N >> M;
        cout << factorial(M) / (factorial(N) * factorial(M - N)) << '\n';
    }
 
}

 

 

[2]

2차원 배열을 이용하는 방법

2차원 배열 bridge를 만들어주고 bridge[N][M]은 서쪽의 사이트가 N개이고, 동쪽의 사이트가 M개일 때 다리를 놓을 수 있는 경우의 수를 저장해준다.

N=1 일 경우(서쪽 사이트가 1개일 때)에는 동쪽 사이트의 개수가 다리를 놓을 수 있는 경우의 수가 되기 때문에 

for문을 이용해서 적절한 배열의 위치에 맞는 값을 넣어준다.

* bridge[1][x] = x

N=2 일 경우 서쪽 사이트의 최상단의 위치를 우측 사이트의 최상단에 연결하면 서쪽에 남은 사이트는 1개가 되고 남은 1개를 우측 사이트에 연결하는 방법을 더해주면 된다.

* bridge[2][2] = bridge[1][1] = 1

* bridge[2][3] = bridge[1][2] = 2

* bridge[3][5] = bridge[2][4] + bridge[2][3] + bridge[2][2] = 10

...

#include <iostream>
using namespace std;
 
int bridge[31][31];
 
int main() {
    int T, N, M;
    
    // 왼쪽 사이트가 하나면 오른쪽 사이트의 개수만큼만 다리 연결 가능
    for (int i = 1; i <= 30; i++) {
        bridge[1][i] = i;
    }
 
    // 왼쪽 사이트가 2개 이상이면 
    // 왼쪽 최상단이 오른쪽 최상단에 연결되었을 경우, 그 다음에 연결되었을 경우...고려
    for (int i = 2; i <= 30; i++) {
        for (int j = 1; j <= 30; j++) {
            for (int k = j - 1; k > 0; k--) {
                bridge[i][j] = bridge[i][j] + bridge[i - 1][k];
            }
        }
    }
    
    cin >> T;
    
    while (T--) {
        cin >> N >> M;
        cout << bridge[N][M] << '\n';
    }
 
}
 

 

Memo

위 문제는 백준에서 실버V 수준의 문제인데 아직은 어렵다.

이번 방학에 열심히해서 골드까지 올라가는 것이 목표다. 힘내서 매일 백준 풀이와 포스팅을 진행해야겠다.