백준2012 - 등수 매기기

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

2012번: 등수 매기기

그리디 알고리즘으로 풀었다.

1등부터 n등까지 학생들을 배치해야 하는데 학생들의 불만을 최소화하여 줄을 세우는 문제다.

입력받은 수를 소팅한 후 1등부터 n등까지 차례대로 빼주어 절댓값을 취해 답에 더해주면 된다.

 

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

int main() {
	int n;
	vector<int> v; //등수를 입력받을 변수
	long long int ans = 0; //답을 출력할 변수

	//원하는 등수를 n번 입력받는다.
	cin >> n;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		v.push_back(num);
	}
    

	sort(v.begin(), v.end()); //입력받은 등수를 오름차순으로 소팅한다.


    //입력받은 수를 1등부터 n등까지 각각 빼서 절댓값을 취한 후 더한다. 
	for (int i = 1; i <= n; i++) {
		ans = ans + abs(i - v[i - 1]);
	}
    
    
	cout << ans;
}