본문 바로가기

백준

백준2012 - 등수 매기기

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

 

2012번: 등수 매기기

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

www.acmicpc.net

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

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;
}

'백준' 카테고리의 다른 글

백준2870 - 수학숙제  (0) 2019.06.19
백준17213 - 과일서리  (0) 2019.06.19
백준11729 - 하노이 탑 이동 순서  (0) 2019.06.11
백준1541 - 잃어버린 괄호  (0) 2019.06.11
백준1389 - 케빈 베이컨의 6단계 법칙  (1) 2019.06.11