[백준- 12854번] 홍준이는 물리를 좋아해 - Java

문제 링크

https://www.acmicpc.net/problem/12854

문제

티어: 골드 2
알고리즘: 그리디, 수학

입력

첫째 줄에 정점의 개수를 나타내는 n과 간선의 개수를 나타내는 m이 주어집니다.

둘째 줄에 i번째 정점의 가중치를 나타내는 n개의 정수가 공백을 사이에 두고 주어집니다.

셋째 줄부터 간선의 정보를 나타내는 3개의 정수가 m개의 줄에 걸쳐서 주어집니다.

정점의 개수는 1개 이상 500개 이하이며, 간선의 개수는 0개 이상 n(n-1)/2개 이하입니다. 중복되는 간선은 주어지지 않습니다. 정점의 가중치는 1보다 크거나 같고 1,000,000보다 작거나 같으며, 간선의 가중치는 1보다 크거나 같고 1,000보다 작거나 같습니다. 그래프에서 정점의 번호는 1번부터 n번까지 순서대로 매겨져 있습니다.

출력

밀도가 최대가 되는 유도 부분그래프의 밀도를 소수 6번째 자리까지 출력한다.

풀이

밀도가 최대가 되는 유도 부분그래프의 밀도를 구해야 한다.

정답부터 말하면, 두 정점을 잇는 유도 부분 그래프가 최적 해가 된다.

간단히 증명해 보면,

각 정점의 가중치가 모두 100만(최대)이고,
각 간선의 가중치가 모두 1(최소)이며,
간선의 개수가 n-1개 일 때 (연결 그래프의 최소 조건)

1,000,000 * n / (n - 1) 이 공식의 2부터 순차적으로 대입해 보자,

그 값이 작아지는 것을 볼 수 있다.

최적의 조건임에도 n이 증가할수록 밀도가 작아진다는 것은 정점의 개수가 최소일 때 밀도를 최대로 만들 수 있음을 뜻한다.

그래서 두 정점을 잇는 유도 부분 그래프가 최적 해가 된다.

더 자세한 증명은 이 링크를 들어가 보길 바란다.

나는 이 문제를 2시간 동안 풀지 못해서 결국 해설을 봤다.

탑-다운 방식으로 어떤 정점을 제거해 나가야 할까?에만 집중했고, 나아갈수록 벽에 막혀 멘탈이 탈탈 털렸다.

만약 바텀-업으로 접근하여 정점을 추가하는 것이 과연 밀도를 높일까?라는 의문을 조금이라도 품었으면 풀었을 것이다.

문제의 원자 단위로 의심해 보는 습관을 가져야 겠다.

소스 코드

import java.io.*;
import java.util.*;

public class Main {
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int m = Integer.parseInt(st.nextToken());
      
      int[] v = new int[n + 1];
      StringTokenizer st2 = new StringTokenizer(br.readLine());
      
      for(int i=1; i<=n; i++) {
          v[i] = Integer.parseInt(st2.nextToken());
      }
      
      double result = -1;
      for(int i=0; i<m; i++) {
          StringTokenizer st3 = new StringTokenizer(br.readLine());
          int a = Integer.parseInt(st3.nextToken());
          int b = Integer.parseInt(st3.nextToken());
          int eW = Integer.parseInt(st3.nextToken());
          
          result = Math.max(result, (v[a] + v[b]) / (double) eW);
      }
      
      System.out.printf("%.6f", result);
  }
}