BOJ 1010 (S5) 다리 놓기

문제 요약

강 서쪽에서 동쪽으로 다리를 놓을 때, 겹치지 않고 설치할 수 있는 모든 경우의 수를 구해보자.
(단, 강의 서쪽 지점 수는 동쪽 지점 수보다 같거나 작다.)

풀이 방향

흔히 nCr이라고 부르는 조합 Combination을 이용하면 쉽게 풀리는 문제이다.

순열,조합 등의 문제에서는 뽑고 뽑히는 방향이 매우 중요하다.
즉, 강의 서쪽과 동쪽의 지점 수를 각각 n,r 중 어디에 배치해야할 지 잘 생각해보아야 한다.

조합으로 해결할 수 있음을 알았다면, 조합계산기에 대입하면서 예제의 값이 맞는지 확인해봐도 좋다.

제출 답안

#include <iostream>
using namespace std;

int main() {
    int t; cin >> t;
    for(int i=0; i<t; i++) {
        int n,r;
        long double sum=1; //nCr = n! / (n-r)!r!
        cin >> r >> n;
        for(int j=n; j>n-r; j--)
            sum*=j;
        for(int j=r; j>=1; j--)
            sum/=j;
        cout << (int)(sum+0.5) << '\n';
    }
    return 0;
}

답안 해설

우선 조합의 정의에 따라 동쪽 지점 수를 n, 서쪽 지점 수를 r으로 설정한다.

그 다음은 nCr을 활용하여 해결하면 된다.
나는 정의를 그대로 나타낸 식 nCr = nPr/r!을 활용했다.
단순히 n!/(n-r)!r! 으로 풀어도 좋고, 식을 정리(소거)해서 풀어도 된다.

이때 결과값을 int형으로 선언하면 최종적으로 원하는 값이 제대로 나오지 않는 경우가 많은데, 자료형 크기 문제 뿐만 아니라, 연산과정에서도 오류가 생기기 때문이다.

우리가 수학문제를 풀때는 5x4x3/3/2/1을 순서대로 계산하지 않고 5x(4/2)x(3/3)x1 등등 사칙연산에 위배되지 않는 선에서 임의로 식을 변형해서 계산하지만, j--형태로 반복되는 for문은 오직 차례대로 계산하기 때문에 유리수값을 정수값으로 버림하게 된다.

즉, 교환법칙과 결합법칙을 사용할 수 없기 때문에, 나는 int형 대신 double형으로 선언하고, 최종 출력 전에 int형으로 강제형변환을 해주었다.

이때도 버림 케이스를 고려해서 0.5를 더해줬다.

이 문제와 관련된 좋은 글
반례를 못찾겠습니다 (BOJ 1010 (S5) 다리 놓기)

추가로 읽어보면 좋은 내용

• 조합 Combination
• 이항정리
• 파스칼 삼각형
• 하키스틱 법칙