문제 배경

나무 막대를 활용하여 정삼각형을 구성하는 방법에 대한 문제입니다.

문제 설명

n개의 나무 막대가 주어집니다. 이 중 4개의 막대를 선택하여 정삼각형을 만들 수 있는 경우의 수를 구하세요. 정답은 10⁹+7로 나눈 나머지를 출력합니다.

입력 형식

첫 번째 줄에는 막대의 개수 n이 주어집니다. 두 번째 줄부터 n개의 줄에 걸쳐 각 막대의 길이 a_i가 주어집니다.

출력 형식

정삼각형을 만들 수 있는 경우의 수를 10⁹+7로 나눈 나머지를 출력합니다.

예제 #1

예제 입력 #1

4
1
1
2
2

예제 출력 #1

1

해결 방법

정삼각형을 만들기 위해서는 다음 조건을 만족해야 합니다:

1. 두 개의 동일한 길이의 막대(변 A, B)가 삼각형의 양변을 구성
2. 나머지 두 막대의 길이 합이 첫 번째 막대 길이와 같아야 함(변 C = C1 + C2)

조합 계산 절차:

1. 각 길이별 막대 개수를 배열에 저장
2. 주요 변수:
   • counts: 길이별 막대 개수
   • min_len: 최소 막대 길이
   • max_len: 최대 막대 길이
3. 길이 i에 대해:
   • 해당 길이 막대가 2개 이상인 경우만 처리
   • j를 min_len부터 i/2까지 순회하며 조합 계산
4. 조합 경우의 수:
   • j ≠ i-j: C(counts[i], 2) × counts[j] × counts[i-j]
   • j = i-j: C(counts[i], 2) × C(counts[j], 2)

코드 구현

#include<iostream>
#include<algorithm>
using namespace std;
const long long MOD = 1000000007;

int main() {
    long long n, total = 0, min_len = 1e6, max_len = 0;
    cin >> n;
    long long counts[1000010] = {0};

    for(int i=0; i<n; i++) {
        long long len;
        cin >> len;
        counts[len]++;
        min_len = min(min_len, len);
        max_len = max(max_len, len);
    }

    for(int i = min_len+1; i <= max_len; i++) {
        if(counts[i] < 2) continue;
        long long side_comb = counts[i] * (counts[i]-1) / 2 % MOD;

        for(int j = min_len; j <= i/2; j++) {
            if(j == i-j) {
                if(counts[j] >= 2) {
                    long long base_comb = counts[j] * (counts[j]-1) / 2 % MOD;
                    total = (total + side_comb * base_comb) % MOD;
                }
            } else {
                if(counts[j] && counts[i-j]) {
                    total = (total + side_comb * counts[j] % MOD * counts[i-j]) % MOD;
                }
            }
        }
    }
    cout << total;
    return 0;
}