문제 소개
n, r, k가 주어졌을 때, n개의 대상 중 r개를 선택하는 모든 방법의 수를 구하되, 특정한 k개는 반드시 함께 포함되어야 하는 조건이 붙는 문제입니다.
입력 : n = 8, r = 5, k = 2
출력 : 960
입력 : n = 6, r = 2, k = 2
출력 : 2
일반적인 순열 계산과 달리, 이 문제에는 지정된 k개의 요소가 항상 하나의 묶음으로 함께 등장해야 한다는 추가 조건이 있습니다. 따라서 코드를 작성하기 전에 먼저 수학적 공식을 도출하는 것이 핵심입니다.
접근 방법: 공식 유도하기
핵심 아이디어는 k개의 요소를 하나의 블록으로 취급하는 것입니다. 이렇게 하면 각 경우의 수를 곱셈 법칙으로 결합할 수 있습니다.
- 블록 내부 정렬: k개의 요소끼리의 순서는 k! 가지입니다.
- 블록의 위치: 선택된 r개의 자리 중 블록이 들어갈 수 있는 위치는 (r − k + 1)가지입니다.
- 나머지 자리 채우기: 남은 (r − k)개의 자리는 나머지 (n − k)개의 요소에서 순서를 고려해 뽑아야 하므로 P(n − k, r − k) 가지입니다.
따라서 최종 공식은 다음과 같습니다.
답 = k! × (r − k + 1) × P(n − k, r − k)
여기서 P(x, y)는 x개 중 y개를 순서 있게 선택하는 순열의 개수를 의미합니다.
C++ 코드 예제
#include <bits/stdc++.h>
using namespace std;
int fact(int n){ // 팩토리얼을 계산하는 함수
if(n <= 1)
return 1;
return n * fact(n-1);
}
int npr(int n, int r){ // 순열 P(n, r)을 계산하는 함수
int pnr = fact(n) / fact(n - r);
return pnr;
}
int countPermutations(int n, int r, int k){ // 도출한 공식 적용
return fact(k) * (r - k + 1) * npr(n - k, r - k);
}
int main(){
int n = 8;
int r = 5;
int k = 2;
cout << countPermutations(n, r, k);
return 0;
}
실행 결과
960
코드 설명
위 코드는 세 가지 함수로 구성되어 있습니다.
- fact(): 재귀 호출을 통해 숫자의 팩토리얼을 계산합니다. n이 1 이하이면 1을 반환하는 것이 종료 조건입니다.
- npr(): 팩토리얼을 활용해 순열 P(n, r) = n! / (n − r)! 을 계산합니다.
- countPermutations(): 앞서 유도한 공식인 k! × (r − k + 1) × P(n − k, r − k)를 그대로 구현하여 최종 답을 반환합니다.
예를 들어 n = 8, r = 5, k = 2인 경우, 2! × 4 × P(6, 3) = 2 × 4 × 120 = 960이 되어 기대한 출력과 일치합니다.
마무리
이번 글에서는 n개 중 r개를 선택할 때 특정 k개가 항상 함께 오도록 하는 순열의 개수를 구하는 문제를 다루었습니다. k개를 하나의 블록으로 묶는 발상을 통해 공식을 유도하고, 이를 C++ 프로그램으로 구현했습니다.
동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 작성할 수 있습니다. 이 튜토리얼이 여러분의 문제 해결에 도움이 되기를 바랍니다.