문제
월간 향유회의 특별 행사로 참가자 $N$명이 두 팀으로 나뉘어 줄다리기하기로 했다! $A_{ij}$는 $i$번 참가자와 $j$번 참가자 간의 팀워크 수치를 의미한다.
줄다리기는 청팀과 백팀으로 나누어 진행하는데, 운영진은 모든 참가자가 하나의 팀에 속하고 두 팀 모두에 한 명 이상이 속하도록 팀을 나누려고 한다.
이때, 같은 팀에 속하는 서로 다른 두 참가자 간의 팀워크 수치의 최솟값이 가장 크도록 팀을 나누려고 한다. 고뇌에 빠진 운영진을 대신해서 그 값이 얼마인지 계산해 보자!
입력
첫째 줄에 참가자의 수 $N$이 주어진다. $(3 \leq N \leq 2\ 000)$
둘째 줄부터 $N$개의 줄에 $N \times N$ 배열 $A$가 주어진다. $A_{ij}$는 $i$번 참가자와 $j$번 참가자 간의 팀워크 수치를 의미하는 정수이다. $(1 \leq A_{ij} \leq 10^{6} \ (i \neq j);$ $A_{ii} = 0;$ $A_{ij} = A_{ji})$
출력
같은 팀에 속하는 서로 다른 두 참가자 간의 팀워크 수치의 최솟값이 가질 수 있는 최댓값을 출력한다.
예제 입력 1
3 0 87 36 87 0 91 36 91 0
예제 출력 1
91
1번 참가자는 홀로, 2번 참가자와 3번 참가자는 팀을 이루면 $A_{23} = 91$이 가장 낮은 팀워크 수치이고 같은 팀에 속하는 서로 다른 두 참가자 간의 팀워크 수치의 최솟값을 이것보다 크도록 팀을 나누는 법은 없다.
예제 입력 2
4 0 1 2 3 1 0 2 1 2 2 0 4 3 1 4 0
예제 출력 2
2
1번 참가자와 4번 참가자가 팀을 이루고, 2번 참가자와 3번 참가자가 팀을 이루면 두 쌍의 팀워크는 각각 $3$, $2$이므로 팀워크의 최소값은 $2$이고, 같은 팀에 속하는 서로 다른 두 참가자 간의 팀워크 수치들의 최솟값을 이것보다 크도록 팀을 나누는 법은 없다.
출처
Contest > BOJ User Contest > 월간 향유회 > 월간 향유회 2024. 02. -겨울 운동회 편- B번
- 문제를 만든 사람: rustiebeats
- 문제를 검수한 사람: chogahui05, jyheo98, kiwiyou, lky7674, pjshwa, snrnsidy, utilforever