백준 2012번 C++ 풀이

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

2012번: 등수 매기기

시간 제한	메모리 제한	solved.ac 티어
2초	256MB	실버 3

문제

2007년 KOI에 N명의 학생들이 참가하였다. 경시일 전날인 예비소집일에, 모든 학생들은 자신이 N명 중에서 몇 등을 할 것인지 예상 등수를 적어서 제출하도록 하였다.

KOI 담당조교로 참가한 김진영 조교는 실수로 모든 학생의 프로그램을 날려 버렸다. 1등부터 N등까지 동석차 없이 등수를 매겨야 하는 김 조교는, 어쩔 수 없이 각 사람이 제출한 예상 등수를 바탕으로 임의로 등수를 매기기로 했다.

자신의 등수를 A등으로 예상하였는데 실제 등수가 B등이 될 경우, 이 사람의 불만도는 A와 B의 차이 (|A - B|)로 수치화할 수 있다. 당신은 N명의 사람들의 불만도의 총 합을 최소로 하면서, 학생들의 등수를 매기려고 한다.

각 사람의 예상 등수가 주어졌을 때, 김 조교를 도와 이러한 불만도의 합을 최소로 하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다.

출력

첫째 줄에 불만도의 합을 최소로 할 때, 그 불만도를 출력한다.

---

예상 등수와 실제 등수가 최대한 비슷해야 하는 문제이다. 어떻게 하면 최대한 비슷해질까? 그리디적으로 생각해서 그냥 예상등수와 최대한 비슷한 실제 등수를 부여해주면 된다. 예상등수를 1등이라고 적은 사람이 3명이 있다면, 1, 2, 3등을 부여해주면 되는 일이다.

 

예상 등수가 1, 1, 1, 2, 3이라고 하자. 설명한 방식대로면 1,1,1,2,3으로 주면 된다. 그런데, 2와 3으로 적은 사람들을 자기 등수에 맞게 배치해주는게 더 이득처럼 보일 수도 있다. 하지만, 결과적으로 같은 값을 가진다. 1, 1, 1, 2, 3의 경우, 불만도의 합은 7이다. 만약 2와 3을 자기 등수에 맞게 배치했다면 1, 2, 3, 1, 1이다. 하지만, 이런 경우에도 불만도의 합은 7이다. 결국 최대한 예상 등수와 비슷하게 등수를 매겨주면 되는 것이다. 

 

그러면 어떻게 예상 등수와 최대한 비슷하게 등수를 매기느냐? 정렬해주면 그만이다.

 

또한 테스트 케이스가 50만까지 들어오기 때문에, int형의 경우 오버플로우가 날 것 같아, long long형으로 선언해주었다. 이후 int로 바꾸어 제출해보니 틀린 것으로 나오는 걸 보아, 오버플로우가 나는 것 같다.

 

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

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int tc;
    long long ans = 0;
    vector<int> v;
    
    cin >> tc;
    for(int i = 0; i < tc; i++) {
        int temp;
        cin >> temp;
        v.push_back(temp);
    }

    sort(v.begin(), v.end());

    for(int i = 0; i < tc; i++) {
        ans += abs(v[i] - i - 1);
    }

    cout << ans;
}