네온 사인( BOJ 8907 )

문제 : https://www.acmicpc.net/problem/8907

8907번: 네온 사인

 

문제 파악하기

N개의 꼭지점 중 3개의 꼭지점을 골라 삼각형을 만들었을 때, 모든 간선의 색이 동일한 경우의 수를 구하는 문제입니다. N이 최대 1,000이기 때문에 처음 보면 크지 않아 보이지만, 1000개의 정점 중 3개의 정점을 선택할 수 있는 경우의 수는 대략 1.6억 가지 경우의 수가 있습니다. 어마어마한 경우의 수이며, 이정도 규모라면 컴퓨터도 1초 안에 모든 경우를 확인하기 힘들다고 할 수 있습니다. 심지어 이번 문제는 여러 테스트케이스가 한 번에 주어지기 때문에 좀 더 효율적인 알고리즘이 필요합니다. 이런 경우에는 수학의 힘을 빌릴 수 있습니다.

 

문제 해결하기

사실 모든 간선이 같은 색인지 확인하는 건 조금 오래걸립니다. 하지만 서로 다른 색의 간선을 가진 경우의 수를 파악하는 건 조금 쉽습니다. 생각해보면 삼각형을 이루는 3개의 선분 중 하나라도 다른 색이기 위해서는 삼각형의 정점 3개 중 2개에서는 서로 다른 2가지 색의 선분이 사용되어야 합니다. 그리고 나머지 한 곳에서는 항상 똑같은 색의 선분이 사용되게 됩니다. 이 점을 활용해 우리는 모든 정점에서 빨간색 선분과 파란색 선분을 하나씩 선택할 수 있는 경우의 수를 전부 구한 다음 절반만 구하면 우리가 원하는 값을 얻을 수 있습니다. 절반만 구하는 이유는 항상 삼각형의 두 정점에서 서로 다른 색깔의 선분이 사용되기에 하나의 삼각형이 두 번씩 구해지기 때문입니다. 이렇게 간단하게 예외 경우를 구한 다음에는 모든 경우의 수(_NC₃)에서 빼주면 됩니다.

 

소스코드

#include <stdio.h>
#include <string.h>
#include <vector>
#define NMAX 1010
using namespace std;
 
int T, N, t, ret;
 
int blue;
int red[NMAX];
 
int main() {
    scanf("%d", &T);
    while(T--) {
        // init
        ret = 0;
        memset(red, 0, sizeof(red));
        
        
        // input
        scanf("%d", &N);
        for(int i=1;i<=N;i++) {
            for(int j=i+1;j<=N;j++) {
                scanf("%d", &t);
                
                red[i] += t;
                red[j] += t;
            }
        }
        
        // solve
        for(int idx=1;idx<=N;idx++) {
            blue = (N-1) - red[idx];
            
            // (빨간색+파란색) 조합 찾기
            ret += red[idx]*blue;
        }
        
        // 전체 경우의 수 - (빨간생+파란색) 조합
        printf("%d\n",  (N*(N-1)*(N-2))/6 - ret/2);
    }
}
 

후기

N의 범위가 작아서 쉽게 도전했다 고민을 하게 된 문제입니다. 항상 문제에서 원하는 경우의 수를 직접 구할 필요가 없다는 점이 문제를 풀기 위한 중요한 포인트라고 생각합니다.