[백준 15903번] 카드 합체 놀이 (java)

백준 15903번 : 카드 합체 놀이

15903번: 카드 합체 놀이

크게 어렵지 않은 문제.

문제를 보자마자 우선순위 큐를 사용해야겠다는 생각이 들었다.

카드 중에서 제일 작은 수 두 개를 뽑아서 합을 구하는 과정을 반복하면 되기 때문이다.

우선순위 큐는 매번 제일 작은 값을 찾을 때 유용하게 쓰일 수 있다.

 

 

알고리즘 : 

1. 우선순위 큐에 카드를 모두 넣는다.

2. 카드 중에서 제일 작은 두 수를 뽑은 뒤, 그 합을 구한 다음, 다시 우선순위 큐에 합을 두 번 넣어주면 된다.

   이 때, 구한 합을 큐에 두 번 넣어주는 이유는 기존의 뽑은 두 카드의 수가 합으로 갱신되기 때문이다.

   그러므로, 카드 두 개를 꺼냈다가 -> 그 합으로 갱신시키고 -> 다시 두 카드를 집어넣는 과정

   이라고 생각하면 된다.

 

소스코드 :