1417번

1417번 - 국회의원 선거

몇 개를 써가면서 규칙을 찾으려고 노력하다 보니,

첫번째로는 큰수들과 교환작업을 한 뒤, 같은 숫자들과 교환작업을 해야하는 우선순위가 있다는 것을 알았다.

또 큰 수 중에서 가장 큰 수와 교환작업을 하는게 더 이득이라는 것을 알게되었다.

따라서 처음에 sort 함수를 통해서 가장 큰 수와 지속적으로, 표를 바꿔주고,

그 후에 같은 값들이 존재하면, 바꿔주는 방식으로 문제를 풀었다.

<정답 코드>

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n, ans;
 
int main()
{
    scanf("%d", &n);
    vector<int> v;
    int x;
    for (int i = 1; i <= n; i++)
    {
        if (i == 1)
        {
            scanf("%d", &x);
        }
        else
        {
            int k;
            scanf("%d", &k);
            v.push_back(k);
        }
    }
 
    
    while (true)
    {
        sort(v.begin(), v.end());
        bool chk = false;
        for (int i = v.size()-1; i >=0; i--)
        {
            if (x <= v[i])
            {
                x++;
                v[i]--;
                ans++;
                chk = true;
                break;
            }
        }
        if (!chk)
        {
            break;
        }
    }
 
    printf("%d\n",ans);
    
    return 0;
}