카드 정렬하기(그리디) - 백준 골드4

- 카드 정렬하기 문제

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

 

- 풀이

걸린 시간 : 15~20분

import java.io.*;
import java.util.*;
public class Main {

    public static int M;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken());

        PriorityQueue<Integer> pQ = new PriorityQueue<>();
        int sum = 0;
        int card;
        for(int i = 0; i < M; i++){
            card = Integer.parseInt(br.readLine());
            pQ.offer(card);
        }

        while(!pQ.isEmpty()){
            if(pQ.size() == 1){
                break;
            }
            int firstCard = pQ.poll();
            int secondCard = pQ.poll();

            int newCard = firstCard + secondCard;
            sum += newCard;
            pQ.offer(newCard);
        }

        bw.write(String.valueOf(sum));
        br.close();
        bw.close();
    }
}

이 문제는 PriorityQueue의 성질만 안다면 굉장히 쉽게 풀리는 문제이다.

문제에서 비교하는 경우를 구하는 것이니, 함정을 조심하자!

 

이 문제를 쉽게 풀고나서, 다른 문제들을 시도했으나,,,

1시간 30분이 넘도록 문제를 어떻게 풀어야 할지를

모르는 문제들을 만나면서,,, 포기했다,,,

 

푼사람들의 코드를 봐도 이해가 잘 안되어서

파트너 분과 오늘 뇌를 다 썼음을 인정하고 스터디를 끝냈다.

 

언제쯤 문제들이 쉬워보일까...

의기소침해지는 하루다.