두 지점 X와 Y 사이에 n개의 중간 기차역이 있다고 가정해 봅시다. 이때 기차가 s개의 역에 정차하되, 어떤 두 정차역도 서로 인접하지 않도록 배치하는 방법의 수를 구하는 것이 이 글의 핵심 문제입니다. 이 문제를 다양한 접근 방식으로 풀어보며, 정차 가능한 역의 조합 수를 계산하는 방법을 자세히 설명하겠습니다.
문제 해결 접근 방법
예를 들어 중간역이 총 8개 있고, 그중 3개의 역에 기차가 정차하는 경우의 수를 구한다고 해보겠습니다.
n = 8, s = 3
기차가 정차할 수 없는 역은 (n - s), 즉 5개가 남습니다.
정차할 수 없는 5개의 역을 A, B, C, D, E라고 하면, 이 역들 사이와 양 끝을 포함해 총 6개의 빈 자리(점선 위치)가 생깁니다. 이 6개의 자리 중에서 3개의 정차역을 배치하면 어떤 두 역도 연속해서 인접하지 않게 됩니다. 따라서 경우의 수는 다음과 같습니다.
6C3 = fact(6) / [fact(3) × fact(3)] = (6 × 5 × 4) / (3 × 2 × 1) = 20
즉, X 지점과 Y 지점 사이에서 3개의 정차역을 배치하는 방법은 총 20가지입니다. 몇 가지 예시를 살펴보겠습니다.
입력 : n = 15, s = 4 출력 : 495 입력 : n = 8, s = 3 출력 : 20
C++ 구현 예제
#include<bits/stdc++.h>
using namespace std;
int main(){
int n = 8, s = 3;
int flag1 = 1, flag2 = 1, temp = s, ans;
// 'n-s+1'개의 위치 중에서 's'개를 선택
int x = n - s + 1;
while (x != (n - 2 * s + 1)) {
flag1 = flag1 * x;
x--;
}
while (temp != 1) {
flag2 = flag2 * temp;
temp--;
}
ans = flag1 / flag2;
if ((n - s + 1) >= s)
cout << "Number of ways : " << ans;
else
cout << "not possible to find";
return 0;
}실행 결과
Number of ways : 20
코드 상세 설명
위 C++ 코드의 동작 과정을 단계별로 나누어 살펴보겠습니다.
전체 역의 개수를 n에, 정차할 역의 개수를 s에 입력받습니다.
flag1과 flag2 변수를 1로 초기화하고, s의 값을 temp 변수에 저장합니다.
flag1에는 분자에 해당하는 값, 즉 (n-s+1)부터 (n-2s+2)까지의 곱을 계산합니다.
flag2에는 분모에 해당하는 s!(팩토리얼) 값을 계산합니다.
flag1을 flag2로 나눈 최종 결과를 출력합니다.
여기서 한 가지 주의할 점은, 선택 가능한 자리의 개수(n - s + 1)가 정차하려는 역의 수(s)보다 작으면 조합 자체가 성립하지 않으므로 "not possible to find"라는 메시지를 출력하도록 처리했다는 것입니다.
마무리
이번 글에서는 기차가 중간역에 정차하되 어떤 두 정차역도 연속되지 않도록 배치하는 방법의 수를 구하는 문제를 다루었습니다. 조합 공식을 활용한 수학적 접근 방식과 이를 C++로 구현하는 전체 과정을 함께 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 작성할 수 있습니다.