[java] 탐욕알고리즘 연습 - 3

// Fence Repair p.68
/**
널빤지 N개를 자르려고 한다. 필요한 길이는 L1, L2, L3는 배열로 주어진다.
널빤지 N개의 Ln의 길이로 자르려고 할 때 최소 비용을 구하라.
N = 3, L = {8,5,8}
21을 13 과 8로 자르는 비용은 21
13을 5, 8로 자르는 비용 13
총 비용은 34다

탐욕 알고리즘으로 풀 수 있다. 
- 가장 짧은 널빤지 노드와 그 다음으로 짧은 널빤지의 노드는 형제면 된다.

**/
import java.io.*;

class Main {
  public static void main(String[] args) throws IOException {
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int ans = 0, N = 3;
    int[] L = {8, 5, 8};

    // 널빤지가 1개가 될때까지 
    while (N > 1) {
      // 가장 짧은 널빤지 mil1, 다음으로 짧은 널빤지 mil2를 구함.
      int mil1 = 0, mil2 = 1;
      if (L[mil1] > L[mil2]) {
        int tmp = mil1;
        mil1 = mil2;
        mil2 = tmp;
      }

    //3번째 배열부터 또 mil1, mil2보다 작은 것들이 있는지 확인하고 있다면 위치를 갱신한다.
    for (int i = 2; i < N; i++) {
      if (L[i] < L[mil1]) {
        mil2 = mil1;
        mil1 = i;
      }
      else if (L[i] < L[mil2]) {
        mil2 = i;
      }
    }

    // L[mil1] + L[mil2] 병합 (제일 작은 서로를 합침)
    int t = L[mil1] + L[mil2];
    ans += t;
    bw.write("ans : " +  ans + "\n");
    if (mil1 == N - 1) {
      int tmp = mil1;
      mil1 = mil2;
      mil2 = tmp;
    }

    L[mil1] = t;  // mil1을 합친값을 넣어서 커지게 만든다. (합쳐졌으니.)
    L[mil2] = L[N-1];  // mil2는 가장 큰 값을 넣는다. (왜지??)
    N--;
    }

    bw.write("ans : " +  ans + "\n");
    bw.close();
    br.close();
}