[백준] 15903 - 카드 합체 놀이(JAVA)

1. 소요시간 : 5분.
2. 문제 사이트 : 백준
3. 문제 수준 : 실버 1
4. 문제 유형 : 자료 구조, 그리디 알고리즘, 우선순위 큐
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/15903
8. 푼 날짜 : 2023.03.17

1. 사용한 자료구조 & 알고리즘

우선순위 큐를 사용했다.

2. 사고과정

문제를 그냥 이해하자마자 5초도 안돼서 우선순위 큐가 떠올랐다. 아마 얼마전에 https://www.acmicpc.net/problem/1715 이 문제에게 호되게 당한 적이 있어서 그럴거다.
이 문제를 당시에 풀었던 풀이과정은 https://velog.io/@anwlro0212/백준-카드-정렬하기-JAVA 에 있다.

그 당시의 충격이 너무 컸던 나머지 remind 를 잘했다. 덕분에 문제 유형을 쉽게 파악할 수 있었다.

3. 풀이과정

1. 우선순위 큐에 숫자를 다 넣어준다.
2. 우선순위 큐에서 숫자 2개를 빼서 더해주고, 그 더한 값을 2번 우선순위 큐에 넣어준다.
   (더해지고 빼지는 유입, 유출량이 같고 n 이 2 이상이므로 nullpointerexception 은 생각하지 않아도 됐다.
3. 그걸 m 번동안 완료한 후에는 우선순위 큐의 값을 모두 더해준다.

4. 소스코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		StringTokenizer st;

		st=new StringTokenizer(br.readLine());

		int n=Integer.parseInt(st.nextToken());
		int m=Integer.parseInt(st.nextToken());
		st=new StringTokenizer(br.readLine());

		PriorityQueue<Long> pq=new PriorityQueue<>();
		for(int i=0;i<n;i++) 
			pq.add(Long.parseLong(st.nextToken()));

		for(int i=0;i<m;i++) {
			long temp=pq.poll()+pq.poll();
			pq.add(temp);
			pq.add(temp);
		}

		long sum=0;
		while(!pq.isEmpty())
			sum+=pq.poll();

		System.out.println(sum);



	}
}

5. 결과

처음에 overflow 가 날 것을 생각하고 long 으로 제출했다.
이후 맞은 다음에 int 로 바꿔서 제출했는데 역시 틀렸다고 나왔다.

6. 회고

이전에 한 번 크게 당했던 문제와 비슷한 유형이 나왔을 때 다행히 잘 푼것으로 보아 문제의 유형을 잘 이해하고 파악한 것 같다. 역시 망치로 머리를 한 번 크게 맞은 것 같은 기분이 드는 문제는 이후에도 깨달음을 얻어서 잘 안틀리는 경향이 있는 것 같다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212