백준 1010 다리 놓기 / C++

문제 : 1010

풀이 point

이항 계수와 같은 문제이다. 단 N과 M의 팩토리얼 범위가 int를 벗어날 수 있으므로 long long으로 설정해주면 된다.

풀이 방법

재귀, for문, dp등의 방법으로 풀 수 있다.

코드

//백준 1010, 다리 놓기

#include <iostream>

int main (){

    long long T;
    std::cin >> T;
    while(T--){
        long long N, M;
        std::cin >> N >> M;
        long long ans{1}; long div{1};
        if(M-N >= N){
            for(auto i{M-N+1}; i<=M; ++i){
                ans *= i;
            }
            for(auto i{1}; i<=N; ++i){
                div *= i;
            }
            std::cout << ans/div << '\n';
        }
        else{
            for(auto i{N+1}; i<=M; ++i){
                ans *= i;
            }
            for(auto i{1}; i<=M-N; ++i){
                div *= i;
            }
            std::cout << ans/div << '\n';
        }
    }

    return 0;
}

2025-01-23T01:23:06.098Z