[C++][백준 BOJ]1715_카드 정렬하기.

문제 번호

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

1715번: 카드 정렬하기

 

 

 

알고리즘 분류

 그리디(greedy), 자료구조(HEAP)

 

문제 풀이

 그리디 알고리즘과 힙(Heap) 자료구조를 모두 알아야 풀 수 있던 문제같다.

처음 들었던 생각은 가장 작은 값들부터 더하여서 큰값들은 가장 적은 횟수로 더해져야 한다는 것이였다.

문제는 처음에는 주어진 값들을 오름차순으로 정렬하여 시작한다하여도 계산이 진행되는 중간중간에 항상 첫 값을 가장 작은값으로 유지해야 한다는 것이였다.

 이때 사용한것이 힙(Heap) 자료구조이다.  힙(Heap) 중에서도 우선순위 큐(Priority_Queue)를 사용하여 구현한 최소 힙(Min Heap)을 사용할 것이다.

 

 우선순위 큐는 값을 삽입하면서 정렬되기 때문에 따로 정렬을 해줄 필요가 없다.

void Insert(priority_queue<int, vector<int>, greater<int>> &card,int N)
{
    for(int i=0; i<N; i++)
    {
        int num; cin >> num;
        card.push(num);
    }
}

 오름차순으로 정렬되는 우선순위 큐를 사용했기때문에 우선순위 큐의 top과 그 다음값을 더해주어야 한다. 

int Solution(priority_queue<int, vector<int>, greater<int>> &card,int N)
{
   int answer=0;

   for(int i=0; i<N-1; i++)
   {
       int num1 = card.top(); card.pop();
       int num2 = card.top(); card.pop();
       int sum = num1 + num2;
       
       answer += (sum);
       card.push(sum);
   }

    return answer;
}

 

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int Solution(priority_queue<int, vector<int>, greater<int>> &card,int N)
{
   int answer=0;

   for(int i=0; i<N-1; i++)
   {
       int num1 = card.top(); card.pop();
       int num2 = card.top(); card.pop();
       int sum = num1 + num2;
       
       answer += (sum);
       card.push(sum);
   }

    return answer;
}

void Insert(priority_queue<int, vector<int>, greater<int>> &card,int N)
{
    for(int i=0; i<N; i++)
    {
        int num; cin >> num;
        card.push(num);
    }
}

int main()
{
    priority_queue<int,vector<int>,greater<int>> card;  
    int N; cin >> N;    
    Insert(card,N);    
    cout << Solution(card, N);

    return 0;
}

 

특이사항

 평소에 힙(Heap)을 자주 사용하지않아서 해결방법을 바로 알 수 없었다.

자료구조와 STL 공부를 꾸준하게 해줘야겠다.