[99클럽 코테 스터디 24일차 TIL] #힙6

24일 차입니다. 전역 후에 집에 있는 시간이 길어지다 보니 하루하루 꾸준히 무언가를 할 게 있다는 사실이 감사하게 여겨지는 것 같습니다. 오늘도 열심히 해보겠습니다.

 

 

문제 설명

---

 

후보 수 n이 주어지고 후보들의 지지자들이 차례대로 주어집니다. 그중 기호 1번인 다솜이라는 친구가 1위후보가 되기 위해 최소한으로 매수해야 하는 사람의 수를 구하는 문제입니다.

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

 

 

생각 흐름

---

스토리텔링식의 문제였기 때문에 문제에서 물어보는 바가 무엇인지 정확히 파악하려고 했습니다.

 

우선, 후보 수 n이 주어진다고 하고 기호 1번인 다솜이가 제일 많은 득표수를 얻기 위해 얼마나 많은 사람을 매수해야 하는지가 궁금한 문제였기 때문에 문제에서 제공하는 정보대로 하나하나 코드를 작성해 보았습니다.

 

여기서 다솜이의 지지자의 수가 제일 첫 번째로 입력이 된다는 점에서 int dasom;이라는 변수를 선언하여 따로 받아주었고 다음 후보자들의 표 수는 다솜이를 제외한 n-1번 반복문을 돌려서 입력받았습니다.

 

문제의 포인트라고 생각하는 점은 결국은 득표 수의 크기 비교를 하는 것이기 때문에 우선순위 큐 pq를 하나 선언하여 득표 수들을 pq에 저장해 주었습니다.

 

우선순위 큐의 특징을 생각해서 pq.top()에 가장 큰 수가 오기 때문에 dasom의 득표수가 가장 많아지는 순간까지 while 문을 돌려야겠다는 생각을 하였고 while (pq.top() >= dasom)이라는 조건문을 걸어서 pq.top()이 dasom보다 크거나 같다면 계속  조건문이 돌아가게 설정을 해주었습니다.

 

위 조건 안에서 pq.top()에 -1을 한 값을 pq에 다시 넣고 pq.top()은 pq.pop()을 통해 제거해 주는 식으로 코드를 작성하였으며 매수자 수 cnt라는 변수를 선언하여 이를 1개씩 늘리고 또한 dasom 변수의 값도 1을 증가시켜 주었습니다.

 

이렇게 코드를 마무리하였습니다.

 

#include <bits/stdc++.h>
using namespace std;

int n, dasom, cnt; // 후보 수 n, 다솜이의 표 개수 dasom, 매수해야 하는 인원수 cnt
priority_queue <int> pq;

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

    cin >> n >> dasom;
    
    for (int i = 1; i < n; i ++) {
        int a;
        cin >> a;
        pq.push(a);
    }
    
    while (pq.top() >= dasom) {
        pq.push(pq.top()-1); // pq에서 가장 큰 값을 1 줄여서 다시 넣어줌
        pq.pop(); // 가장 큰 값 제외
        cnt++; // 한명 매수
        dasom++; // 다솜 표 획득
    }
    
    cout << cnt << "\n";

    return 0;
}

 

 

근데 여기서, 오류가 발생하는 겁니다. 제가 간과한 것이 있었는데 다솜이가 혼자 출마를 한다면, 매수자를 구할 필요가 없다는 예외사항을 생각을 안 했던 것이었고,

 

다솜이가 혼자 출마를 했다면 pq의 size()가 0, 즉 pq가 empty() = 1일 것이라는 점을 이용해서 조건문에 조건을 추가해 주어 마무리하였습니다.

 

// 우선순위 큐 사용 (가장 큰 값이 top에 위치)

#include <bits/stdc++.h>
using namespace std;

int n, dasom, cnt; // 후보 수 n, 다솜이의 표 개수 dasom, 매수해야 하는 인원수 cnt
priority_queue <int> pq;

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

    cin >> n >> dasom;
    
    for (int i = 1; i < n; i ++) {
        int a;
        cin >> a;
        pq.push(a);
    }
    
    while (!pq.empty() && pq.top() >= dasom) {
        pq.push(pq.top()-1); // pq에서 가장 큰 값을 1 줄여서 다시 넣어줌
        pq.pop(); // 가장 큰 값 제외
        cnt++; // 한명 매수
        dasom++; // 다솜 표 획득
    }
    
    cout << cnt << "\n";

    return 0;
}

 

 

공부한 내용 정리

---

생각해 보면 뭔가 힙이라는 개념에 대해 정확히 알지는 못한다는 생각을 하였습니다.

heap이 정확히 무엇이고 왜 이게 사용되는지를 누군가에게 설명한다면 못할 것 같은 생각이 들었달까요,,

 

따로 heap에 대해 글을 쓰며 공부해 보기로 했습니다.

 

https://dev-jsy.tistory.com/39