(매일 BOJ) C++ 1010번 다리 놓기

이번 문제는 실버 5 난이도의 다리 놓기 문제이다.

접근법

이 문제는 강 동쪽에 있는 사이트가 A, 강 서쪽에 있는 사이트가 B 라고 가정한 조합 문제로 볼 수 있다.

따라서 이 조합을 코드로 구현하면 쉽게 해결할 수 있을 것이다.

 

1차 코드

# include <bits/stdc++.h>
using namespace std;


int main(void){
    ios::sync_with_stdio(0); cin.tie(0);
    int N;
    cin >> N;
    for (int i = 0; i < N; i++ ){
        int a,b;
        cin >> b >> a;
        int combination = 1;
        for (int j = b+1; j <= a; j++) combination *= j;
        for (int o = 1; o <= a-b; o++ ) combination /= o;
        cout << combination << '\n';

    }
}

최종 코드

조합 코드를 단축시킬 수 있었던 방법이 있었다. 

combination *= (a - j + 1);

combination /= j;

 

이를 사용하여 작성하였다.

# include <bits/stdc++.h>
using namespace std;


int main(void){
    ios::sync_with_stdio(0); cin.tie(0);
    int N;
    cin >> N;
    for (int i = 0; i < N; i++ ){
        int a,b;
        cin >> b >> a;
        long long combination = 1;
        for (int j = 1; j <= b; j++) {
            combination *= (a - j + 1);
            combination /= j;
        }
        cout << combination << '\n';

    }
}