C 언어로 기차 정차역 조합의 수 구하기 – 연속 정차 금지 조건

문제 개요

문제 설명 − 기차가 전체 n개의 역 중 r개의 역에 정차할 때, 어떤 두 정차역도 서로 연속(인접)하지 않도록 정차하는 경우의 수를 구하는 프로그램을 작성합니다.

문제 풀이

이 프로그램은 기차가 정차할 수 있는 모든 경우의 수를 계산합니다. 기차는 지점 X에서 지점 Y까지 이동하며, 두 지점 사이에는 총 n개의 역이 있습니다. 기차는 이 n개의 역 중 r개의 역에 정차하게 되는데, 이때 반드시 지켜야 할 조건이 하나 있습니다. 바로 두 정차역이 연속해서 이어지면 안 된다는 것입니다.

이러한 조건을 만족하는 경우의 수는 순열 공식을 변형한 조합 공식을 이용해 직접 계산할 수 있습니다.

C(n−r+1, r) = (n−r+1)! ∕ (r! × (n−2r+1)!)

구체적인 예시를 통해 살펴보겠습니다.

입력 : n = 16 , r = 6
출력 : 462

설명 − 16개의 역 중에서 연속되지 않도록 6개의 정차역을 선택하는 방법의 수는 위 공식으로 계산한 결과인 462가지입니다.

알고리즘

입력 : 전체 역의 개수 n, 기차가 정차할 역의 개수 r
1단계 : n과 r의 값으로 C(n−r+1, r) = (n−r+1)! / (r! × (n−2r+1)!) 를 계산합니다.
2단계 : 표준 출력 함수를 사용해 계산 결과를 화면에 출력합니다.

예제 코드

#include<stdio.h>
int main(){
    int n = 16, s = 6;
    printf("Total number of stations = %d\nNumber of stopping station = %d\n", s, n);
    int p = s;
    int num = 1, dem = 1;
    while (p!=1) {
        dem*=p;
        p--;
    }
    int t = n-s+1;
    while (t!=(n-2*s+1)) {
        num *= t;
        t--;
    }
    if ((n-s+1) >= s)
        printf("Possible ways = %d", num / dem);
    else
        printf("no possible ways");
}

실행 결과

Total number of stations = 16
Number of stopping station = 6
Possible ways = 462

위 코드는 분자와 분모를 각각 곱셈으로 누적한 뒤 나누어 조합 값을 효율적으로 계산합니다. 또한 (n−s+1) ≥ s 조건을 검사하여, 주어진 역 수로는 연속되지 않게 정차역을 선택하는 것이 불가능한 경우 "no possible ways"라는 메시지를 출력하도록 처리했습니다.