문제 개요
정수 n이 주어졌을 때, 세로로 n개의 선과 가로로 n개의 선이 서로 교차하여 총 n²개의 교차점이 만들어집니다. 이 문제의 목표는 이 교차점들에 4개의 항목을 배치하되, 어느 하나의 행(가로줄)이나 열(세로줄)에도 둘 이상의 항목이 포함되지 않도록 하는 배치 방법의 총 개수를 구하는 것입니다.
예제를 통해 문제를 살펴보겠습니다.
입력
n = 4
출력
24
설명
n이 4일 때, 4×4 격자의 교차점 위에 4개의 항목을 서로 다른 행과 열에 하나씩만 배치하는 경우의 수는 24가지입니다.
접근 방법
이 문제를 해결하려면 먼저 n개의 가로선 중에서 항목이 놓일 4개의 선을 선택해야 하며, 이는 조합 기호로 nC4가지 방법에 해당합니다.
각 가로선마다 n개의 세로선이 교차하고 있으므로, 첫 번째로 선택한 가로선에 항목을 놓을 수 있는 방법은 n가지입니다. 두 번째 가로선에서는 이미 사용한 열을 피해야 하기 때문에 n-1가지, 세 번째는 n-2가지, 네 번째는 n-3가지 방법으로 배치할 수 있습니다.
따라서 전체 배치 방법의 수는 다음과 같이 계산됩니다.
nC4 × n × (n-1) × (n-2) × (n-3)
참고로 이 공식은 n이 4 이상일 때만 성립합니다. n이 4보다 작으면 서로 다른 행과 열에 4개의 항목을 배치하는 것이 불가능하기 때문입니다. 또한 이 식은 곱셈과 나눗셈만 사용하므로 시간 복잡도 O(1)로 상수 시간 안에 결과를 구할 수 있어 매우 효율적입니다.
C++ 구현 예제
#include <iostream>
using namespace std;
long long placeItems(int n) {
return (1LL * (1LL *
((n) * (n - 1) * (n - 2) * (n - 3)) / (4 * 3 * 2 * 1)) *
((1LL * (n) * (n - 1) * (n - 2) * (n - 3))));
}
int main() {
int n = 4;
cout << "세로 " << n << "개, 가로 " << n << "개의 선이 만드는 교차점에 ";
cout << "4개의 항목을 배치하는 방법의 수는 " << placeItems(n) << "가지입니다.";
return 0;
}실행 결과
세로 4개, 가로 4개의 선이 만드는 교차점에 4개의 항목을 배치하는 방법의 수는 24가지입니다.
코드 설명
placeItems 함수는 앞서 유도한 공식을 그대로 구현한 것입니다. nC4 부분은 n×(n-1)×(n-2)×(n-3)을 4!인 24로 나누어 계산하며, 이후 같은 곱을 한 번 더 곱해 최종 결과를 얻습니다. 곱셈 과정에서 값이 int 범위를 초과할 수 있으므로 1LL을 곱해 long long 타입으로 승격시켜 오버플로우를 방지한 점이 특징입니다.
마무리
이처럼 조합과 순열의 개념을 활용하면 격자 위의 배치 문제를 단순한 수식 하나로 해결할 수 있습니다. 반복문이나 백트래킹 없이 O(1) 연산만으로 답을 구할 수 있다는 점에서, 수학적 사고가 알고리즘 효율을 크게 좌우한다는 좋은 예시가 됩니다.