백준 1417. 국회의원 선거

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

1417번: 국회의원 선거

 

분류별로 문제를 푸는 방식의 단점을 느낀 문제다.

요즘 그리디 문제를 풀고있기 때문에 그리디 분류에서 풀어서 당연히 그리디 방식으로 풀려고 고민했는데 

그리디로 풀었을때 엄청 어려운 문제다. (풀수있는지도 모르겠다)

 

결국 브루트포스로 아주 쉽게 풀었다.

n이 최대 1000이기 때문에 처음부터 브루트포스로 풀까 고민했지만 애초에 그리디 문제 푸는것을 연습하고 있기때문에 그리디로 풀려했는데 그냥 브루트포스로 푸는게 훨씬 좋은것 같다.

 

반복문안에서 다솜이보다 득표수가 크거나 같은 사람을 찾아서 표를 하나씩 뺴오면되고, 그런 사람이 없으면 탈출하면된다.

O(N^2)이고 n은 최대 1000이라 문제없이 풀수있다.

 

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

int n;
vector<int> v;

int main()
{
    cin >> n;
    v.resize(n);
    for(int i = 0; i < n; i++)
        cin >> v[i];

    // 후보가 한명일때 매수 할필요 없음
    if(n == 1)
    {
        cout << 0;
        return 0;
    }

    int ans = 0;
    while(true)
    {
        int biggest = 0;
        int biggest_idx = 0;
        // 득표수 가장 많은 사람 찾음
        for(int i = 1; i < n; i++)
        {
            if(v[i] > biggest)
            {
                biggest = v[i];
                biggest_idx = i;
            }
        }

        if(biggest >= v[0])
        {
            v[0]++;
            v[biggest_idx]--;
            ans++; // 매수한 사람 수
        } // 다솜이가 가장 득표수 많음
        else
            break;
    }

    cout << ans;

}

 

풀고난후 좀 찾아봤는데

그리디로 분류된 이유는 우선순위 큐를 사용해서이다.

input들을 우선순위큐에 저장하면 가장 큰 값을 일일히 찾지 않아도 가장 높은 값을 알수있고,

표를 하나빼올때마다 우선순위큐의 front값과 비교하면 되므로 그리디 문제라고 생각할수있다.