[백준] 16678 - 모독

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

16678번: 모독

 

처음에 각 입력에 대해 중복이 없는 줄 알고 풀었다가 반례를 찾아서 다시 수정했다.

 

문제를 잘 읽어보면, "Defile" 한 번으로 모든 국회의원을 박탈시키려면, 모든 국회의원의 명예 점수가 연속되어야 한다. 당연히 중간에 중복이 있을 수 있다.

 

그렇다면 우리가 해야할 일은 입력을 연속되게 만들어야 한다. 그러기 위해서는 먼저 정렬을 진행하자. 다음 예제로 살펴보자.

7
5 5 3 1 3 5 7

정렬하면

1 3 3 5 5 5 7가 된다.

눈으로만 봤을 때 연속되게 하려면, 1 2 3 4 5 5 6가 되어야 할 것이다.

즉, 숫자를 하나씩 중가시켜 가며 만약 건너뛰는 구간이 있다면(1 -> 3) 연속되게 만들어 주면 된다.

 

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

long long n, ans, a[100001];
vector<long long> v;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        long long k;
        cin >> k;
        v.push_back(k);
    }
    sort(v.begin(), v.end());
    int idx = 1;
    for (int i = 0; i < v.size(); i++) {
        if (v[i] < idx) {
            continue;
        } else if (v[i] == idx) {
            idx++;
        } else {
            ans += abs(idx - v[i]);
            v[i] = idx;
            idx++;
        }
    }
    cout << ans;
}