[백준] 2012번: 등수 매기기(그리디)

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

2012번: 등수 매기기

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int B = 1;		// 실제 등수
		long sum = 0;	// 불만도 합 최솟값
		int[] arr = new int[N];
		
		for(int i=0; i<arr.length; i++)
			arr[i] = scan.nextInt();
		
		Arrays.sort(arr);
		
		for(int i=0; i<arr.length; i++) {
			sum += Math.abs(arr[i] - (i+1));			
		}
		
		System.out.println(sum);
		scan.close();
	}

}

풀이

간단한 문제였다. 불만도 합의 최소값을 구하는 문제이다.

불만도의 합이 최소가 되려면 학생이 예상한 등수와 실제 등수가 최솟값이 되도록 정해주면 된다.

따라서 학생이 예상한 등수를 오름차순으로 정렬하고, 작은것부터 1등, 2등, 3등, ... 빼주면 된다.

* 문제에서 N의 범위가 500,000 인데, 만약 모든 학생이 자신의 등수를 1로 예상할경우,

|1-500,000| x 500,500 이 되어서 int의 범위를 벗어난다.

따라서 불만도의 자료형을 long 으로 선언한다.