[백준]1715번 카드 정렬하기

1715번: 카드 정렬하기

• 책 합치던 문제랑 비슷한 것 같다.
  • 차이점 : 그 문제는 붙어있는 것 끼리만 합치는거였음. 이게 훨씬 더 쉽다

가장 적게 비교하는 경우의 횟수를 구하라.

(20)

문제 풀이

• 현재 가장 작은 두 묶음끼리 합쳐나가면 되는 문제였다.(그리디)
• 이 때 주의할 것은, 카드 묶음이 하나만 있는 경우인데, 이때는 비교대상자체가 없는 것이기 때문에 0번의 비교를 하는 것으로 해야한다.

public class Main{
    public static int n;
    public static PriorityQueue<Integer> q = new PriorityQueue<>();

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;
    public static void setting() throws IOException {
        n = Integer.parseInt(br.readLine());
        for(int i = 0;i<n;i++){
            q.add(Integer.parseInt(br.readLine()));
        }
    }
    public static int solve(){
        int sum = 0;
        if(q.size()==1) return 0;
        int one = 0,sec=0;
        while(q.size()>1){
            one = q.poll();
            sec = q.poll();
            q.add(one+sec);
            sum += (one+sec);
        }
        return sum;
    }

    public static void main(String[] args) throws IOException{
        setting();
        System.out.println(solve());
    }
}