24433번 - 정수 그래프 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (하단 참고) | 512 MB | 42 | 12 | 12 | 29.268% |
문제
Alice와 Bob은 "정수 그래프"를 이용한 놀이를 즐겨한다.
"정수 그래프"는 노드와 간선의 수가 무한한 방향성이 없는 그래프인고, 다음과 같이 정의한다.
- 노드: 모든 양의 정수 $z$에 대응되는 고유한 노드가 존재한다. 따라서, 임의의 노드는 해당 노드의 정수로 나타낼 수 있다.
- 간선: 어떤 노드 $x$와 $y$가 아래 조건 중 하나를 충족하면 둘 사이에 간선이 존재한다.
- $x > y$ 라면: $x$의 $1$이 아닌 약수 중 가장 작은 수가 $d$일 때, $x/d = y$라면 두 노드 사이에 간선이 존재한다. 해당 간선의 길이는 $d$이다.
- $x < y$ 라면: $y$의 $1$이 아닌 약수 중 가장 작은 수가 $d$일 때, $y/d = x$라면 두 노드 사이에 간선이 존재한다. 해당 간선의 길이는 $d$이다.
- 일반적인 그래프와 마찬가지로 최단 경로를 정의하며, $dist(x, y)$는 두 노드 $x$, $y$ 사이의 최단 경로의 길이를 나타낸다. 이때 길이는 해당 최단 경로에 속한 간선의 길이의 총합이다.
예를 들어, 아래 그림은 "정수 그래프"의 일부를 보여 준다. 가령 노드 $10$과 $20$사이에는 길이 $2$인 간선이 존재하고, 노드 $25$와 $5$사이에는 길이 $5$인 간선이 존재한다.
두 아이는 정수 그래프를 이용해서 아래와 같은 놀이를 하기로 했다:
- 먼저 Alice가 $n$개의 양의 정수 $v_1, v_2, \dots, v_n$를 고른다 (같은 정수를 여러 번 고를 수도 있다). 그리고 $D$를 다음과 같이 정의한다: \(D = \sum_{1 \le i \lt j \le n} dist(v_i, v_j)\) 즉, D값은 Alice가 고른 정수들 각 쌍에 대하여 그에 해당하는 두 노드 사이의 최단 경로 길이의 총합이다.
- 다음으로, Bob이 $n$개의 정수 중 하나를 빼고, 나머지 $n-1$개의 정수에 대하여 마찬가지로 $D$값을 새로 계산한다. 즉, $1$이상 $n$이하의 정수 중 $k$번째 정수를 빼고, 새로 계산할 $D$값을 $E(k)$라고 한다면: \( E(k) = \sum_{1 \le i \lt j \le n, i \ne k, j \ne k} dist(v_i, v_j) \)가 된다. 이때 Bob은 $E(k)$값이 최소가 되도록 하고 싶다.
예를 들어 Alice가 $v_1 = 10$, $v_2 = 15$, $v_3 = 25$를 골랐을 경우를 살펴보자.
- $dist(v_1, v_2) = 5$, $dist(v_2, v_3) = 8$, $dist(v_3, v_1) = 7$이 되어 $D = 5+8+7 = 20$이다.
- Bob이 $v_1$을 제거하면 $v_2, v_3$만 남게 되어 $E(1) = 8$이다.
- Bob이 $v_2$을 제거하면 $v_1, v_3$만 남게 되어 $E(2) = 7$이다.
- Bob이 $v_3$을 제거하면 $v_1, v_2$만 남게 되어 $E(3) = 5$이다.
입력으로 Alice가 선택한 $n$개의 정수가 주어졌을 때, Bob이 달성할 수 있는 $E(k)$의 최소값을 구해보자.
입력
첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 입력은 두 줄에 걸쳐 주어진다. 첫 줄에 $n$이 주어지고 둘째 줄에 Alice가 고른 $n$개의 정수 $v_1, v_2, \dots, v_n$이 공백으로 구분되어 주어진다.
출력
각 테스트 케이스의 정답을 각 줄에 출력한다.
서브태스크 1 (10점)
- $1 ≤ T ≤ 10$
- $1 ≤ n ≤ 500$
- $1 ≤ v_1, v_2, \dots, v_n ≤ 1\,000\,000$
서브태스크 2 (20점)
- $1 ≤ T ≤ 10$
- $1 ≤ n ≤ 100\,000$
- $1 ≤ v_1, v_2, \dots, v_n ≤ 1\,000\,000$
예제 입력 1
6 3 10 15 25 4 24 36 20 30 6 10 20 30 30 20 10 4 12 18 24 36 8 10 10 20 20 20 30 30 30 4 1 1 1 2
예제 출력 1
5 46 40 22 94 0
- 예제 1: $25$를 빼면 $10$과 $15$사이 거리가 $5$이므로 $E(k)$값이 최소가 된다.
- 예제 2: $36$을 빼는 것이 최선이다.
- 예제 3: 두 개의 $30$중 하나를 빼면 된다.
- 예제 4: $24$를 빼거나 $36$을 빼면 된다.
- 예제 6: $2$를 빼는 것이 최선이다.
시간 제한
- Java 8: 2 초
- Python 3: 5 초
- PyPy3: 5 초
- Java 8 (OpenJDK): 2 초
- Java 11: 2 초
- Kotlin (JVM): 2 초
- Java 15: 2 초
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호