BOJ#6195 Fence Repair

BOJ#6195 Fence Repair

* 문제

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

(Olympiad > USA Computing Olympiad > 2006-2007 Season > USACO November 2006 Contest > Gold 1번)

* 풀이

최초 생각한 알고리즘은 가장 긴 널빤지를 가장 빨리 만드는 것이었습니다.

(늦게 처리할 수록 큰 값이 Cost에 포함되기 때문에)

그러나, 위 알고리즘의 반례는 아래와 같습니다.

ex) 5 / 1, 2, 3, 4, 5 일 때

<처음 생각한 알고리즘>

1단계 : 15 -> 5, 10 (15)

2단계 : 10 -> 4, 6 (10)

3단계 : 6 -> 3, 3 (6)

4단계 : 3 -> 2, 1 (3)

Cost : 34

<반례>

1단계 : 15 -> 7, 8 (15)

2단계 : 7 -> 3, 4 (7)

2단계 : 8 -> 5, 3 (8)

3단계 : 3 -> 2, 1 (3)

Cost : 33

---------------------------------------

두 경우 Cost의 차이는 1입니다.

반례에서 처음 생각한 알고리즘과 비교했을 때,

5가 1단계가 아니라 2단계에 나오는 대신(+5)

3이 3단계가 아닌 2단계에서 나오고 (-3)

2와 1이 4단계가 아닌 3단계에서 나오기 때문입니다. (-2 -1)

 : +5 - 3 - 2 - 1 = -1

따라서 무조건 큰 널빤지를 가장 빨리 만드는 것이 최적의 해가 아님을 알게 되었습니다.

한편, 

널빤지는 항상 2개의 널빤지로 나누어지므로

널빤지를 자르는 것은 이진 트리에 대응할 수 있는데

여러가지 예에서 관찰해 보았을 때

가장 작은 널빤지와 그 다음으로 작은 널빤지는 최대 depth에서 발견되고

또한, 그 둘은 형제 노드임을 알 수 있습니다.

즉, 정리하자면

최적의 해로 널빤지를 자르는 것은 아래의 성질을 갖고 있음을 알 수 있습니다.

"가장 작은 널빤지와 그 다음으로 작은 널빤지는 가장 깊은 depth에서 형제 노드 관계이다."

따라서 위 성질을 이용하여 가장 작은 널빤지 2개를 조립하면서 최초 하나의 널빤지가 될 때까지 합쳐간다면 필요한 cost를 구할 수 있을 것입니다.

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%236195_FenceRepair/src

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * BOJ#6195 Fence Repair
 * https://www.acmicpc.net/problem/6195
 */

public class Main {

    public static void main(String[] args) throws IOException {

        int N;  // number of planks
        int[] L; // length of plank
        int minIdx1, minIdx2;
        long cost = 0;

        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        L = new int[N];

        for (int i = 0; i < N; i++) {

            L[i] = Integer.parseInt(br.readLine());
        }

        // 널빤지 N이 1개가 될 때까지
        while (N > 1) {

            minIdx1 = 0; // 가장 작은 널빤지 idx
            minIdx2 = 1; // 그 다음으로 작은 널빤지 idx

            if (L[minIdx1] > L[minIdx2]) {

                // swap
                minIdx1 ^= minIdx2;
                minIdx2 ^= minIdx1;
                minIdx1 ^= minIdx2;
            }

            // 가장 짧은 널빤지와 그 다음으로 작은 널빤지를 구한다
            for (int i = 2; i < N; i++) {

                if (L[i] < L[minIdx1]) {

                    minIdx2 = minIdx1;
                    minIdx1 = i;
                } else if (L[i] < L[minIdx2]) {

                    minIdx2 = i;
                }
            }

            // 구한 2개의 널빤지를 합친다. cost 갱신.
            int subCost = L[minIdx1] + L[minIdx2];
            cost += subCost;

            // 널빤지 2개를 합쳤으므로 N = N-1을 해준다.
            // 합친 널빤지는 L[minIdx1]에 넣어주고, 필요 없어진 minIdx2에는 L[N-1] 값을 넣어준다.
            if (minIdx1 == N - 1) {

                // swap
                minIdx1 ^= minIdx2;
                minIdx2 ^= minIdx1;
                minIdx1 ^= minIdx2;
            }

            L[minIdx1] = subCost;
            L[minIdx2] = L[N - 1];

            N--;
        } // while loop

        System.out.println(cost);
    }
}