큐(Queue)
백준 1715번: 카드 정렬하기
cepiloth
2018. 8. 5. 15:27
반응형
https://www.acmicpc.net/problem/1715
1715번: 카드 정렬하기
정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면
www.acmicpc.net
키워드 - 힙, 구현, 우선순위큐
Approach
정수 10 20 40 이 입력으로 들어오고 큐에 쌓이는 순서는 10 20 40
최상위 두개의 값을 pop 을 하여 10 + 20 덧셈을 다시 큐에 넣으면 30, 40
다음 상태에서 30 + 40 = 70
총 비교회수는 100(30 + 70) 이 된다.
Source
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <math.h>
#include <memory.h>
using namespace std;
#define MAX_SIZE 100
#define INF 0x7fffffff
#define CENDL "\n"
#define ll long long
int main() {
cin.tie(0);
std::ios::sync_with_stdio(false);
int n; cin >> n;
priority_queue<int, vector<int>, greater<int> > q;
while (n--) {
int d; cin >> d;
q.push(d);
// 순차적으로 모두 넣어줌
}
int sol = 0;
while (q.size() > 1) {
int a = q.top(); q.pop();
int b = q.top(); q.pop();
sol += a + b;
q.push(a + b);
}
cout << sol << CENDL;
return 0;
}
반응형