문제
알고리즘 캠프에 N명의 학생들이 있다. 이 학생들 중에서는 친한 사이도 있고 어색한 사이도 있다.
선생님은 N명의 학생들끼리 어색한 정도 F(i, j)를 표로 만들었다. 이때 F(i, j)는 i번 학생과 j번 학생 간의 어색한 정도를 의미한다. 모든 학생들의 쌍 (i, j)에 대해서 F(i, j)는 F(j, i)이다.
선생님은 일부 학생들끼리 떠들면 학업 분위기를 해칠 염려가 있어서 친한 친구들의 모임을 찾아서 감시하려고 한다. 이때 친한 친구들의 모임은 아래 조건을 만족해야 한다.
1. 친한 친구들의 모임은 2명 이상 N-1명 이하의 학생들로 구성되어야 한다.
2. 친한 친구들의 모임에서 가장 어색한 두 학생이 어색한 정도가 친한 친구들의 모임에 소속된 학생과 그렇지 않은 학생 간의 어색한 정도보다 항상 낮아야 한다.
예를 들어, A와 B와 C가 있어서 F(A, B) = 8, F(B, C) = 3, F(C, A) = 5라고 하자. 이때 A와 C가 있는 모임은 C가 A보다 B에게 친함을 느끼므로 친한 친구들의 모임이 아니다. 한편 B와 C가 있는 모임은 B, C 간의 사이가 가장 친하므로 친한 친구들의 모임이다.
선생님은 가능한 친한 친구들의 모임을 전부 구하려고 한다. N명의 학생들 사이의 어색한 정도가 주어질 때 가능한 친한 친구들의 모임의 수를 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에 학생의 N이 주어진다. (1 ≤ N ≤ 1,000)
두 번째 줄부터 N개의 줄에는 i (1 ≤ i ≤ N-1)번 학생과 i+1, i+2, …, N번 학생 간의 어색한 정도 F(i, j)가 주어진다. (1 ≤ F(i, j) ≤ 1,000,000)
출력
첫 번째 줄에 친한 친구들의 모임의 수를 출력한다. 답이 32bit integer 범위에 있다는 것은 보장되어 있다.
채점
전체 데이터의 35%는 N ≤ 20을 만족한다.
전체 데이터의 60%는 모든 학생들의 쌍에 대해 어색한 정도가 모두 다르다.
예제 #1
3
8 5
3
1
예제 #2
4
1 3 5
6 4
2
2
예제 #3
5
1 6 5 10
7 8 9
2 4
3
3
출처
ACM-ICPC Daejeon Regional 2015 인터넷 예선 문제 A
로그인해야 코드를 작성할 수 있어요.