Notice
Recent Posts
Recent Comments
Link
«   2025/03   »
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31
Tags
more
Archives
Today
Total
관리 메뉴

끄적끄적

백준 [1715] 카드 정렬하기 본문

코테준비/백준

백준 [1715] 카드 정렬하기

alstj_성공 2022. 9. 1. 18:37

출처 : https://www.acmicpc.net/problem/1715

 

1715번: 카드 정렬하기

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장

www.acmicpc.net

 

그리디 + 우선순위큐

주어진 숫자들을 우선순위큐에 넣고 오름차순 정렬하여 차례대로 뽑아주면서 더해주면 된다.

그래야 작은수부터 나오니까 최소 비교 횟수를 구할 수 있음.

우선순위큐 오름차순 정렬(default는 내림차순) -> priority_queue<int, vector<int>, greater<int>> pq;

* priority_queue는 힙으로 구현할 수 있다.

'코테준비 > 백준' 카테고리의 다른 글

백준 [13164] 행복 유치원  (0) 2022.09.02
백준 [1052] 물병  (0) 2022.09.01
백준 [1759] 암호 만들기  (0) 2022.08.30
백준 [14495] 피보나치 비스무리한 수열  (0) 2022.08.30
백준 [1965] 상자넣기  (0) 2022.08.26