취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2012번 문제인 등수 매기기이다.

문제는 아래 링크를 확인하자.

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

예상등수를 작게 쓴 사람들을 작은 등수에, 크게 쓴 사람들을 큰 수에 쓰는 것이 최선의 전략이 된다.

어떤 두 쌍의 사람 A와 B에 대하여 각자의 예상 등수는 A<B였지만 실제 등수가 A>B인 경우가 있다면 둘의 실제 등수를 바꾸는 것만으로도 불만도를 줄일 수 있기 때문이다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

ll arr[500001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}

	sort(arr, arr + N + 1);

	ll ans = 0;
	for (ll i = 1; i <= N; i++) {
		ans += abs(i - arr[i]);
	}

	cout << ans;
}