문제 소개
세 개의 직선 위에 각각 여러 개의 점이 놓여 있을 때, 이 점들을 이용해 만들 수 있는 삼각형이 총 몇 개인지 구하는 문제입니다.
입력: m = 3, n = 4, k = 5
출력: 205
입력: m = 2, n = 2, k = 1
출력: 10
이 문제는 조합론을 활용하면 하나의 간단한 공식으로 해결할 수 있습니다.
해결 접근 방법
핵심 아이디어는 다음과 같습니다. 세 점이 삼각형을 이루려면 반드시 세 점이 한 직선 위에 있으면 안 됩니다. 따라서 전체 점 중 3개를 뽑는 모든 경우의 수에서, 같은 직선 위에 있는 3점을 뽑는 경우의 수를 빼주면 정답이 됩니다.
이를 공식으로 표현하면 다음과 같습니다.
정답 = C(n+m+r, 3) − [ C(n,3) + C(m,3) + C(r,3) ]
- C(n+m+r, 3): 전체 점(n+m+r개) 중 3개를 선택하는 모든 조합
- C(n,3), C(m,3), C(r,3): 각 직선 위에서만 3개의 점을 선택하는 경우, 즉 일직선상에 놓여 삼각형을 만들 수 없는 경우
C++ 구현 코드
위 접근 방식을 구현한 C++ 코드는 다음과 같습니다.
예제 코드
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
long long fact(long long n) {
if(n <= 1)
return 1;
return ((n % MOD) * (fact(n-1) % MOD)) % MOD;
}
long long comb(int n, int r) {
return (((fact(n)) % MOD) / ((fact(r) % MOD) * (fact(n-r) % MOD)) % MOD);
}
int main() {
int n = 3;
int m = 4;
int r = 5;
long long linen = comb(n, 3); // n개 중 3개를 고르는 조합
long long linem = comb(m, 3); // m개 중 3개를 고르는 조합
long long liner = comb(r, 3); // r개 중 3개를 고르는 조합
long long answer = comb(n + m + r, 3); // 전체 점 중 3개를 고르는 모든 조합
answer -= (linen + linem + liner);
cout << answer << "\n";
return 0;
}
실행 결과
205
코드 설명
먼저 전체 점 n+m+r개 중 3개를 선택하는 모든 조합, 즉 comb(n+m+r, 3)을 계산합니다. 앞서 말했듯이 세 점이 삼각형을 이루려면 세 점이 일직선상에 있으면 안 되므로, 각 직선 내부에서만 3개의 점을 선택하는 경우의 수인 comb(n,3), comb(m,3), comb(r,3)의 합을 구합니다. 전체 조합에서 이 합을 빼면 삼각형을 만들 수 있는 경우의 수만 남게 되고, 이 값을 출력하면 정답을 얻을 수 있습니다.
참고로 위 코드는 값이 작은 경우에는 정상적으로 동작하지만, 팩토리얼 나눗셈에 모듈러 연산을 사용할 때는 수학적으로 정확한 결과를 보장하려면 모듈러 역원(modular inverse)을 이용해 나눗셈을 처리해야 합니다. 실제 경쟁 프로그래밍에서 큰 입력을 다룰 때는 이 점을 유의해야 합니다.
마무리
이번 글에서는 조합론을 활용하여 세 직선 위의 점들로 만들 수 있는 삼각형의 개수를 구하는 방법을 알아보았습니다. 전체 조합에서 일직선상의 조합을 제외하는 간단한 아이디어만으로 문제를 효율적으로 해결할 수 있으며, 동일한 로직은 C, Java, Python 등 다른 언어로도 손쉽게 구현할 수 있습니다. 이 글이 여러분의 문제 해결에 도움이 되기를 바랍니다.