티스토리 뷰

문제 풀이

[BOJ 8907] 네온 사인

RiKang 2018. 1. 25. 13:34

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


풀이 )


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


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


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



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



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


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


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


 최종 코드 )


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 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;
}
cs


'문제 풀이' 카테고리의 다른 글

[BOJ 8907] 네온 사인  (0) 2018.01.25
스택 기본 문제 풀이  (4) 2018.01.22
[BOJ 8901] 화학 제품  (0) 2018.01.22
[BOJ 8911] 거북이  (0) 2018.01.22
[BOJ 8897] Slicing Tree  (0) 2018.01.11
[BOJ 8898] 스포츠 전문 채널 GSK  (0) 2018.01.11