이번 문제는 그리디 알고리즘을 통해 간단하게 해결하였다.

• 입력받은 예상 등수를 오름차순으로 정렬한다.
• 예상 등수를 wish라고 하고 등수를 rank라고 한다면, abs(wish-rank)가 최소가 되기 위해서는 예상 등수 배열의 첫번째 수부터 차례대로 등수를 매긴다.
• 반복문을 통해 차의 절댓값을 모두 더해준다.

Code

#include <iostream>
#include <algorithm>
#include <math.h>
#define MAX 500001
using namespace std;

int n;
int wish[MAX];
int cnt=0;

void Input(){
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>wish[i];
    }
}

void Solution(){
    sort(wish, wish+n);
    for(int i=0; i<n; i++){
        cnt+=abs(i+1-wish[i]);
    }
    cout<<cnt<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    Solution();
    return 0;
}