[백준] 알고리즘 분류(그리디 알고리즘,JAVA)1715번, 카드 정렬하기

문제 링크

1715번: 카드 정렬하기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 카드 묶음을 합칠 때 각 크기의 합만큼 비교를 진행합니다.

2. N개의 카드 묶음을 합칠 때 최소 비교 횟수를 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 우선순위 큐를 이용하여 카드 묶음 크기 낮은 순으로 합치기를 진행합니다.

 

3. 최소 비교 횟수를 결과로 출력합니다.

 

최소 비교 횟수.

 

카드 묶음을 합칠 때 최소로 비교하려면 카드 묶음의 크기가 큰 값을 최소로 사용되어야 합니다.

 

카드 : 20, 50, 100이 존재할 때

 

최소 비교 횟수 : (20 + 50) + (70 + 100) = 240

 

카드 묶음의 크기가 큰 값을 작은 값들보다 많이 사용할 경우

 

(100 + 20) + (120 + 50) = 290

 

보라색 부분에는 카드 묶음 100짜리가 2번 사용되는 것으로 보실 수 있습니다.

 

최소 비교 횟수에서는 1번만 사용되었기 때문에 최소값을 구할 수 있습니다.

 

결과적으로 크기가 작은 카드 묶음부터 합쳐나아가면 최소 비교 횟수를 구할 수 있습니다.

 

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 2

카드 묶음 : 10, 20, 40

 

2. 우선순위 큐를 이용하여 카드 묶음 크기 낮은 순으로 합치기를 진행합니다.

 

우선순위 큐에서는 카드 묶음의 크기 기준 오름차순으로 정렬되도록 하였습니다.

 

크기가 작은 카드 묶음 2개 합치기!

 

10 + 20 = 30

 

카드 묶음 : 30 , 40

 

크기가 작은 카드 묶음 2개 합치기!

 

30 + 40 = 70

 

카드 묶음 : 70

 

모두 합치기 완성!

 

모든 비교 횟수 더하기 = 30(10 + 20) + 70(30 + 40) = 100

 

3. 최소 비교 횟수를 결과로 출력합니다.

 

100을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• PriorityQueue를 사용하여 카드 묶음의 크기를 오름차순으로 저장되도록 하였습니다.
• 카드 묶음의 크기가 낮은 순으로 합치기를 진행하여 최소 비교 횟수를 계산합니다.
• 최소 비교 횟수를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

import java.io.*;
import java.util.*;


public class Main {
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        //입력되는 카드 묶음 우선순위 큐에 저장
        for(int i=0;i<N;i++)
            pq.add(Integer.parseInt(br.readLine()));
        //최소 비교 횟수 구하기
        while(!pq.isEmpty()){
            int cur = pq.poll();
            //남아있는 카드 묶음이 1개일 때
            if(pq.isEmpty()){
                bw.write(answer + "");	//모든 비교 횟수 BufferedWriter 저장
                continue;
            }
            int next = pq.poll();
            cur += next;		//카드 합치기
            answer += cur;
            pq.add(cur);	//합친 카드 묶음 우선순위 큐에 다시 저장
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}