[백준] 1715 - 카드 정렬하기 [그리디]

---

문제

카드 정렬하기 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

43246

14540

11201

33.488%

문제

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

출력

첫째 줄에 최소 비교 횟수를 출력한다.

예제 입력 1 복사

3
10
20
40

예제 출력 1 복사

100

 

---

풀이1 (실패)

 

최초에 시도하여 실패한 코드..

지금 보니 n의 조건이 (1 ≤ N ≤ 100,000) 인데, 0은 왜 넣었나 싶다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(bf.readLine());
        int[] arr = new int[n];

        if (n == 0) {
            System.out.println(0);
            return;
        }

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(bf.readLine());
        }

        Arrays.sort(arr);

        int compareCtn = 0;
        for (int i = 1; i < n; i++) {
            int totalCard = arr[i-1] + arr[i];
            compareCtn += totalCard;
            arr[i] = totalCard;
        }
        System.out.println(compareCtn);
    }
}

위 코드의 진행 구조는 대략 다음과 같다.

1. n을 입력 받는다.

 

2. n개 만큼의 카드 묶음 크기를 배열로 받는다 -> arr 배열

 

3. arr 정렬 -> 2개의 카드 묶음끼리의 비교 횟수는 묶음의 크기만큼이기 때문에,

비교가 되는 카드 묶음을 최대한 작게 만들어 비교를 진행하여야 한다.

그러므로 제일 작은 카드 묶음 순으로 순차적으로 비교하기 위하여 정렬하였다.

 

4.sum 이라는 비교횟수를 누적하여 저장하는 변수를 만듦

 

5. 

n = 5 이고, 각 카드 묶음의 크기가 1, 2, 3, 4, 5 로 정렬 되었을때.

1 + 2 -> sum += 3, 합쳐진 카드 묶음을 i번째에 저장

3 + 3 -> sum += 6, 합쳐진 카드 묶음을 i번째에 저장 

6 + 4 -> sum += 10, 합쳐진 카드 묶음을 i번째에 저장 (해당 알고리즘이 틀리게 되는 시점)

10 + 5 -> sum += 15, 합쳐진 카드 묶음을 i번째에 저장

그러므로, sum은 34 가 되고 출력값으로 34를 출력한다.

 

빨간줄 라인이 정답을 도출하는 풀이2와의 결정적인 차이이다.

 

앞서서 말했지만, 비교 횟수는 "1번 카드묶음 크기 + 2번 카드묶음 크기" 만큼이고, 그렇게 비교된 두개의 카드 더미는 하나로 합쳐진다. 그리고 총 비교횟수를 최소로 만드려면 두개의 카드더미가 최대한 작아야한다.

그러므로, 카드 더미 중 1번째로 작은, 2번째로 작은 카드 더미끼리 비교하여 하나로 합쳐야 하는 것이다.

그런데, 빨간준 시점에서 존재하는 카드 더미는

6, 4, 5 이다. 그런데 처음에 정렬한 그냥 순차적으로만 카드 더미를 더하기 때문에 6 + 4가 된것이다.

사실 이 시점에서는 4개의 카드 더미와 5개의 카드 더미를 먼저 비교하여 합친 후

6개 더미 + 9개 더미 연산이 진행되어야 하는 것이다. 

 

---

풀이1 (성공)

 

정답 풀이이다.

자바의 우선순위 큐는 기본적으로 오른차순 정렬이다.

그러므로 1번째로 크기가 작은 카드 더미, 2번째로 크기가 작은 카드 더미를 순차적으로 꺼낼 수 있고,

비교하여 합쳐진 카드 더미를 우선순위 큐로 바로 넣어서 다른 카드와 또 합쳐질 수 있게 하면 된다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(bf.readLine());

        PriorityQueue<Integer> pr = new PriorityQueue();
        for (int i = 0; i < n; i++) {
            pr.add(Integer.parseInt(bf.readLine()));
        }

        int sum = 0;
        while (pr.size() > 1) {

            Integer min1 = pr.poll();
            Integer min2 = pr.poll();

            sum += (min1+min2);
            pr.add(min1 + min2);
        }

        System.out.println(sum);
    }
}

 

---

반례

case1

n = 5

1,2,3,4,5

 

풀이1, 풀이2 에 따라 결과 값이 달라짐

1 + 2

3 + 3

이후 

6, 4, 5가 남은 상황에서

풀이 1은 6 + 4를 함

---

case2

n = 4

1,2,3,4

 

풀이1, 풀이2 의 결과가 같음

1 + 2

3 + 3

이후 

6, 4만 남으므로 

어차피 6 + 4 밖에 할게 없으므로...