[백준] 알고리즘 분류(그리디 알고리즘,JAVA)15903번, 카드 합체 놀이

문제 링크

15903번: 카드 합체 놀이

---

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 카드를 합치면 각 카드의 값은 더한 값으로 변경됩니다.

2. m번 카드를 합친 뒤에 가장 작은 점수를 결과로 출력합니다.

3. 점수는 n개의 카드의 수를 모두 더한 값입니다.

 

알고리즘 진행 순서.

 

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

 

2. 우선순위 큐를 이용해서 카드의 낮은 값끼리 m번 합치기를 진행합니다.

 

3. 합치기 진행 후, 카드의 합을 결과로 출력합니다.

 

 

합치기

 

가장 작은 값을 구해야하기 때문에 현재 카드의 작은 값 2개를 합칩니다.

 

예를 들어.

 

3 51 5

 

카드를 가장 먼저 합치는 경우는 : 3 , 5 입니다.

 

3 + 5 = 8

 

8 51 8

 

만약 다른 카드가 합쳐진다면? 3 , 51

 

3 + 51 = 54

 

54 54 5

 

결과적으로 m번 합치기를 진행할 때 카드의 값이 가장 작은 2개의 카드를 합치는 것을 반복하면 됩니다.

 

가장 작은 2개의 카드를 합치기 전에 얻기 위해서 PriorityQueue<>를 사용하였습니다.

 

예제입력 1.

 

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

n : 3

m : 1

 

3 2 6

2. 우선순위 큐를 이용해서 카드의 낮은 값끼리 m번 합치기를 진행합니다.

 

PriorityQueue

 

2

3

6

 

합치기 진행!

 

2

3

6

작은 값 : 2, 3

2 + 3 = 5

 

5

5

6

 

3. 합치기 진행 후, 카드의 합을 결과로 출력합니다.

5 + 5 + 6 = 16

 

16을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokeinzer를 이용해서 카드의 값을 띄어쓰기 기준 나누었습니다.
• 카드의 값들을 오름차순 정렬되는 PriorityQueue에 모두 저장하였습니다.
• PriorityQueue를 사용하여 최소 카드 2개를 m번 합치기를 계속 진행합니다.
• m번 합치기 이후 카드 값의 합을 결과로 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

import java.io.*;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main{
    static int n,m;
    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));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        //카드 저장할 우선순위 큐(오름차순 정렬)
        PriorityQueue<Long> pq = new PriorityQueue<>();
        st = new StringTokenizer(br.readLine()," ");
        //모든 카드값 우선순위 큐에 저장
        for(int i=0;i<n;i++)
            pq.offer(Long.parseLong(st.nextToken()));
        //m번 합치기 진행
        for(int i=0;i<m;i++){
            long sum = pq.poll() + pq.poll();	//가장 작은 2개 카드값 더하기
            //2개의 카드 덮어쓰기
            pq.offer(sum);
            pq.offer(sum);
        }
        long answer = 0;
        //m번 합치기 이후 모든 카드의 값 더하기
        while(!pq.isEmpty())
            answer += pq.poll();
        bw.write(answer + "");	//점수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}