[자바/백준 골드4] #1715 카드 정렬하기

🔒 골드4 - #1715 카드 정렬하기

 

📌 테스트케이스 추가 힌트

5
10
20
10
10
40

= 190

4
10
10
10
30

= 110

 

 

✍️ 풀이법

 

해당 문제는 이해했다고 생각해도 헷갈리는 경우가 많았던 것 같다.

 

테스트 케이스를 세우고 문제를 풀 때, 더한 값들을 한 번씩 쓰면서 다 합친 이후.

쓴 값들을 다 더해주어야 답이 나오게 된다는 점을 알고 진행하면, 이해하기 편할 것 같다.

 

첫 번째 케이스를 예로 들자면, 90이 나오는 과정에서 모든 카드가 합쳐지게 된다.

이 후, 파란 값 ( 더한 과정에서 나온 값) 들을 다 합치면 원하는 정답 190 이 나오게 된다.

 

 

 

 

이 문제는 토너먼트 방식을 사용하려하거나, 리그 방식을 사용하려고 하면 안 된다.

왜냐하면, 가장 작은 카드 뭉치부터 뭉쳐주어야, 최솟값이 나오기 때문이다.

 

따라서 카드 뭉치를 뭉치고, 다시 비교해 주는 작업을 해 주어야 한다.

 

 

 

예를들어, 두번째 테스트 케이스를 보자.

단순하게 토너먼트 방식으로 생각하게되면, 정답은 110인데,  120이 나오게 되므로 오답이다.

 

 

그렇다면 어떻게 110이 나오게 할 수 있을까?

 

 

바로

토너먼트가 아닌, 한 뭉치를 합치고 처음부터 새로 비교하는 것이다.

 

첫번째 비교가 끝난 후, 남은 카드 더미는 [ 20, 10, 30 ] 이다. 토너먼트 대로라면 10과 30 을 합쳤지만,

우리는 최솟값을 구해야 하므로, 10과 20을 합치는 것이 맞다.

 

 

따라서, 한 번 합치는 작업 이후에 새로 정렬하고 다시 비교하는 작업이 필요하다.

 

나는 처음에 토너먼트로 풀려고 했었기 때문에 Queue를 사용했었다. 안 된다는 걸 깨달은 이후, 정렬을 자동으로 해 주기 위하여 우선순위 큐 (PriorityQueue)를 사용하여 문제를 해결하였다.

 

 

 

풀이 과정

    1. 작은 순 정렬

    2. 가장 작은 두 덱을 합친다.

    3. 위 과정을 덱의 수가 1이 될때까지 반복한다.

 

 

🗝️ 풀이

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class baekjoon1715 {

    private static int sum = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        List<Integer> decks = new ArrayList<>();

        for (int time = 0; time < N; time++) {
            decks.add(sc.nextInt());
        }

        solve(decks);
        System.out.println(sum);
    }

    public static void solve(List<Integer> decks) {
        PriorityQueue<Integer> queDeck = new PriorityQueue<>(decks);
        sumDecks(queDeck);
    }


    private static void sumDecks(PriorityQueue<Integer> decks) {
        if (decks.size() == 1) {
            return;
        }

        int sumTwin = decks.poll() + decks.poll();
        sum += sumTwin;
        decks.add(sumTwin);

        sumDecks(decks);
    }
}