백준[2012] - 등수 매기기

• 문제: https://www.acmicpc.net/problem/2012
• 분류: 그리디, 정렬
• 난이도: S3
• 소요시간: 10m
• 자아성찰:
  
  • 꽤나 단순한 그리디 문제였다.
  • 예상등수와 실제 등수의 차이의 합을 최소화 하는 문제
  • 예상등수를 높게 생각한 학생에게 높은 등수를 줄수록 차이의 합이 최소가 된다. (그리디)
  • 예상등수를 오름차순 정렬 -> 예상등수 순으로 등수를 매겨 차이 합 구함
  • 이 때, 중요한 것은 정답의 최댓값이었다.
    • N = 500000이므로 모두가 1등을 예상할 경우 정답의 최댓값은 int 범위를 훌쩍 넘어가버린다.
    • 0 + 1 + 2 + ... + 499,999 = 약 1250억
  • 맞왜틀 => 정답의 범위를 확인해보자

 

---

public class B_2012 {

    static int N;
    static int[] arr;
    static long result = 0; // 최대 0..499,999 더한 값이므로 long

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr); // 예상 등수 오름차순 정렬
        for (int i = 1; i <= N; i++) { // 예상 등수가 높은 순부터 실제 등수를 매김
            int n = arr[i];
            result += Math.abs(i - n); // |A - B|
        }
        System.out.println(result);
    }
}