다리 놓기

문제: 다리 놓기 (백준 1010번)

구조 분석

문제를 처음 보고 드는 생각은 “아! 조합 문제이구나!” 였다. 그런데 문제 카테고리가 dynamic programming이어서 우선 dynamic programming으로 풀어보려고 했다. 조합 문제를 dynamic programming에 적용하는 방식은 많지만 제일 먼저 떠올린 생각은 “factorial 계산을 dp table에 저장하여 문제를 풀어보자”였다.

그러나 factorial 계산을 하면 숫자가 커지면서 오버플로우가 발생하여 실패했다.

그래서 그냥 수학문제로 풀기로 했다.
위의 조합 계산 공식을 활용하면 되는데, 여기서 포인트는 factorial 계산을 모두 실시하여 나눠주면 숫자가 너무 커지게 되므로 반복문을 이용하여 계산할 때 매번 소거를 실시해주며 계산하는 것이다.

코드

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#define MAX 30
using namespace std;

int main() {
    int t, n, m;
    long long res;
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> t;

    for (int i=0; i<t; i++) {
        cin >> n >> m;
        res = 1;
        int r = 1;
        for (int i=m; i>(m-n); i--) {
            res *= i;
            res /= r++;
        }
        cout << res << "\n";
    }
    return 0;
}

정리

카테고리는 dynamic programming이지만 수학문제로 푸는 것이 더 쉬운 문제였다. 시간복잡도는 반복문만 따지면 되므로 O(N)이다. 주의할 점은 factorial 계산은 숫자가 너무 커져 오버플로우가 발생할 수 있다는 것이다. 이를 염두해두고 코드를 작성해야 한다.