[백준/Baekjoon] 1715 카드 정렬하기 C++ :: Greedy

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

1715번: 카드 정렬하기

---

1. Logic

항상 작은 값 2개를 선택해서 정렬해야 최소한으로 비교할 수 있게 된다.

 

우선순위 큐는 우선순위가 높은 값을 기준으로 즉 값이 큰 거부터 내림차순으로 정렬해 주는 자료구조이다.

우선순위 큐를 선언과 동시에 greater인자를 붙혀주게 되면 오름차순으로 정렬되기 때문에 문제를 풀기 적절한 자료구조이다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

priority_queue<int, vector<int>, greater<>> card;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n;
    int ans = 0;

    cin >> n;

    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;

        card.push(a);
    }

    while(card.size() != 1) {
        int c1 = card.top();
        card.pop();
        int c2 = card.top();
        card.pop();

        ans += c1 + c2;
        card.push(c1 + c2);
    }

    cout << ans;
}

 

 

---

 

 

3. Feedback

우선순위 큐를 빠르게 떠올려서 쉽게 풀 수 있었다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90