끄적끄적
백준 [1715] 카드 정렬하기 본문
출처 : 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 |