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

 

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

 

---

 

문제

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

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

 

문제

 

 

 

 

 

입출력 예시

입출력 예시

 

입출력 예시

 

 

 

---

 

풀이 | 이항 계수와 파스칼의 삼각형

 

✒  이항 계수란?

✒ 이항 계수란?

 

이항 계수는 수학에서 이항 정리(binomial theorem)와 관련된 계수로, 주어진 두 숫자 n과 r에 대해 이항 계수 nCr 로 나타낸다. 이는 조합(combination) 또는 "n개 중에서 r개를 고르는 방법의 수"를 의미한다.

 

이항 계수는 다음과 같은 공식으로 계산된다.

출처: 나무위키

 

또한, 이항계수는 파스칼의 삼각형(Pascal's Triangle)과도 밀접한 관련이 있다. 파스칼의 삼각형에서 각 숫자는 그 바로 위의 두 숫자의 합으로 구성된다.

 

 

 

 

✒  파스칼의 삼각형(Pascal's triangle)이란?

✒  파스칼의 삼각형이란(Pascal's triangle)?

 

파스칼의 삼각형은 위에서 설명한 이항계수를 삼각형 모양으로 나열한 것이다.

 

파스칼의 삼각형은 아래의 규칙을 따른다.

1. 삼각형의 맨 위(0번째 행)는 하나의 1로 시작한다.
2. 그 다음 행부터는, 각 행의 첫 번째와 마지막 숫자는 1이다.
3. 내부의 숫자는 바로 위의 두 숫자의 합으로 계산된다.

 

파스칼의 삼각형은 이항 계수, 이항 정리 외에도 조합론, 확률론, 대수학에서 유용하게 사용되니 알아두면 매우 좋다!

 

---

이항계수의 공식을 그대로 이용했던 첫 풀이는 실패했다. (실패한 코드는 본문의 마지막에 기록용으로 올려뒀다.)

이유는, 팩토리얼을 계산하는 과정에서 자료형의 범위를 훨씬 넘어버렸기 때문이다. 오버플로!!

(이 문제에선 최대 29! 까지 계산할 수 있어야한다.)

 

 

 

그래서, 간단한 정수로 이루어져 있는 파스칼의 삼각형을 이용하는 방법을 택했다.

dp[N][M] = dp[N - 1][M - 1] + dp[N][M - 1] 이다.

 

#include <iostream>
using namespace std;

int main() {
    int dp[31][31] = {0};

    /* 입력 받기: 테스트 케이스의 개수 */
    int T; 
    cin >> T;

    /* dp 채우기: 파스칼의 삼각형 */
    for (int i = 1; i < 31; ++i) {
        for (int j = i; j < 31; ++j) {
            if (i == 1) {
                dp[i][j] = j;
            }
            else if (i == j) {
                dp[i][j] = 1;
            }
            else {
                dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
            }
        }
    }

    /* 입력 받기: 서쪽(N), 동쪽(M) 사이트 개수 */
    for (int i = 0; i < T; ++i) {
        int N, M;
        cin >> N >> M;
        cout << dp[N][M] << endl;
    }

    return 0;
}

 

 

 

 

💀 오버플로

#include <iostream>
using namespace std;

int main() {
    long long dp[31] = {0};
    
    /* 입력 받기: 테스트 케이스의 개수 */
    int T; 
    cin >> T;

    for (int i = 0; i < T; ++i) {
        
        /* 입력 받기: 서, 동쪽 사이트 개수 */
        int N, M;
        cin >> N >> M;

        for (int j = 0; j <= M; ++j) {
            if (j == 0 || j == 1) {
                dp[j] = 1;
            }
            else {
                dp[j] = j * dp[j - 1];
            }
        }

        long long result = dp[M] / dp[M - N] / dp[N];
        cout << result << endl;
    }

    return 0;
}

 

---