[BOJ 8907] 네온 사인

 2011 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8907 에서 채점할 수 있습니다.

풀이 )

1) '단색 삼각형의 수 = 모든 삼각형의 수 - 두 개의 색이 있는 삼각형의 수' 입니다.

2) '모든 삼각형의 수  = n*(n-1)*(n-2)/6' 입니다. ()

3) '두 개의 색이 있는 삼각형' 은 아래의 두 가지 경우가 있습니다.

 이 두 가지 경우의 공통점을 찾아보면 서로 다른 색의 간선이 연결된 꼭지점이 2개라는 점이 있습니다.

 따라서 위와 같이(서로 다른 색의 두 간선이 한 꼭지점에 연결된 경우의 수) / 2를 구하면 '두 개의 색이 있는 삼각형'의 수를 구할 수 있습니다.

 cnt[i] = 꼭지점 i에 연결된 빨간색 선의 개수

 위와 같은 cnt 배열을 구하면 으로 서로 다른 색의 두 간선이 한 꼭지점에 연결된 경우의 수를 구할 수 있습니다.

 최종 코드 )

// code by RiKang, weeklyps.com
// 2011 ACM-ICPC Daejeon regional - H
// BOJ 8907 네온 사인
 
#include <bits/stdc++.h>
using namespace::std;
 
int n, sum;
int cnt[1005];
 
void solve(){
    scanf("%d",&n);
    
    sum=0;
    for(int i=0; i<n; i++)
        cnt[i] = 0;
    
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            int in;
            scanf("%d",&in);
            cnt[i]+=in;
            cnt[j]+=in;
        }
    }
    for(int i=0; i<n; i++)
        sum+=cnt[i]*(n-1-cnt[i]);
    printf("%d\n",n*(n-1)*(n-2)/6-sum/2);
}
 
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        solve();
    }
    return 0;
}