기차가 여러 중간역을 지날 때, 특정 개수의 역에만 정차하면서도 어느 두 정차역도 서로 붙어 있지 않게 하려면 몇 가지 방법이 있을까요? 이 글에서는 이른바 '정차역 선택' 문제를 조합 공식과 파이썬 코드로 해결하는 과정을 단계별로 살펴보겠습니다.
문제 정의
문제: 두 지점 A와 B 사이에는 중간역이 총 13개 있습니다. 기차가 이 가운데 2개의 중간역에 정차하되, 선택된 두 역이 서로 인접(연속)하지 않아야 한다면 가능한 정차 조합은 모두 몇 가지일까요?
해결 아이디어: 조합 공식 활용
이 문제는 조합론의 고전적인 유형으로, 다음 공식 하나로 깔끔하게 정리됩니다.
n개의 중간역 중 서로 연속되지 않는 p개의 역을 선택하는 경우의 수 = C(n − p + 1, p)
직관적으로 이해해 보겠습니다. 정차하지 않는 13 − 2 = 11개의 역을 일렬로 세우면, 맨 앞과 맨 뒤를 포함해 총 12개의 빈틈(간격)이 생깁니다. 정차할 2개의 역을 이 빈틈 중 서로 다른 위치에 하나씩 끼워 넣으면, 두 정차역이 자동으로 인접하지 않게 됩니다. 따라서 경우의 수는 다음과 같습니다.
C(12, 2) = 12 × 11 ÷ 2 = 66가지
파이썬 구현
# 정차역 조합 계산 함수
def stopping_station(p, n):
num = 1 # 분자
dem = 1 # 분모
s = p
# 분모: p! (팩토리얼) 계산
while p != 1:
dem *= p
p -= 1
# 분자: (n-2s+2)부터 (n-s+1)까지 연속된 s개 수의 곱
t = n - s + 1
while t != (n - 2 * s + 1):
num *= t
t -= 1
if (n - s + 1) >= s:
return int(num / dem)
else:
# 배치가 불가능한 경우
return -1
# 실행부
num = stopping_station(2, 13)
if num != -1:
print("정차 가능한 조합의 수:", num)
else:
print("정차 조합을 만들 수 없습니다")
실행 결과
정차 가능한 조합의 수: 66
코드 상세 설명
- dem(분모): while 반복문으로 p의 팩토리얼(p!)을 계산합니다. p = 2일 때 dem = 2 × 1 = 2가 됩니다.
- num(분자): 변수 t를 n − s + 1부터 n − 2s + 2까지 하나씩 줄여 가며 곱합니다. 즉 연속된 s개의 정수를 곱한 값으로, n = 13, s = 2일 때 12 × 11 = 132입니다.
- 결과 반환: num ÷ dem, 즉 132 ÷ 2 = 66이 최종 답이며, 이는 앞서 본 조합 공식 C(n − s + 1, s)과 정확히 일치합니다.
- 예외 처리: (n − s + 1)이 s보다 작으면, 정차역끼리 인접하지 않게 배치하는 것이 애초에 불가능하므로 −1을 반환해 실패 메시지를 출력합니다.
다양한 입력에서의 활용
이 프로그램은 중간역 수와 정차역 수만 바꾸면 어떤 입력에도 그대로 적용할 수 있습니다. 예를 들어 중간역이 10개이고 3곳에 정차한다면 C(8, 3) = 56가지, 중간역이 20개이고 4곳에 정차한다면 C(17, 4) = 2380가지가 답이 됩니다.
마무리
이번 글에서는 A와 B 사이 13개의 중간역에서 서로 인접하지 않는 2개의 정차역을 고르는 문제를 조합 공식 C(n − p + 1, p)으로 모델링하고, 파이썬으로 구현해 66이라는 결과를 확인했습니다. 핵심은 복잡해 보이는 배치 문제를 '빈틈에 끼워 넣기' 관점의 단순한 조합 계산으로 바꾸는 것이며, 이 아이디어는 비슷한 유형의 조합론 문제에도 폭넓게 응용할 수 있습니다.