백준 BOJ 2012 - 등수 매기기

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

2012번: 등수 매기기

실제 등수가 1,2,3,4,5.... 차가 1로 일정한 증가하는 수열의 형태를 띄고 있고,

문제 입력으로 들어온 수열을 해당 수열과 최대한 비슷한 형태로 구성하는 문제이다.

 

최대한 비슷한 형태 >> 정렬된 배열을 지칭하는 말로,

입력으로 들어온 배열을 정렬해서 인덱스값+1 과 비교해서 불만도의 총 합을 구하면 된다.

 

입력으로 들어온 배열을 구성할 때

$i<j$이고 $N_i > N_j$ 인 상황에서 불만도의 합인 $Total$ 값이

$N_i <= N_j$ 일 때보다 보다 같거나 커지게 되며,

따라서 모든 $i$, $j$ 에 대해서

$N_i <= N_j$이게 정렬하면 문제에서 요구하듯 $Total$을 최소화할수 있다.

 

N의 범위가 50만인 만큼 정렬을 O(NlogN) 에 해야한다는 점과

$Total$을 저장할 변수가 int범위를 넘어감에 따라 long long 자료형을 사용해야한다는 점

두가지에 조심해야 한다.

 

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

int arr[567890] = {0};

int main(){
	int N;
	ll ans = 0;
	
	cin >> N;
	for(int i=1; i<=N; i++){
		cin >> arr[i];
	}
	
	sort(arr+1, arr+N+1);
	
	for(int i=1; i<=N; i++){
		ans += abs(i-arr[i]);
	}
	
	cout << ans;
	return 0;
}