[백준] 2012번 등수 매기기

문제

2007년 KOI에 N명의 학생들이 참가하였다. 경시일 전날인 예비소집일에, 모든 학생들은 자신이 N명 중에서 몇 등을 할 것인지 예상 등수를 적어서 제출하도록 하였다.

KOI 담당조교로 참가한 김진영 조교는 실수로 모든 학생의 프로그램을 날려 버렸다. 1등부터 N등까지 동석차 없이 등수를 매겨야 하는 김 조교는, 어쩔 수 없이 각 사람이 제출한 예상 등수를 바탕으로 임의로 등수를 매기기로 했다.

자신의 등수를 A등으로 예상하였는데 실제 등수가 B등이 될 경우, 이 사람의 불만도는 A와 B의 차이 ( |A-B| )로 수치화할 수 있다. 당신은 N명의 사람들의 불만도의 총 합을 최소로 하면서, 학생들의 등수를 매기려고 한다.

각 사람의 예상 등수가 주어졌을 때, 김 조교를 도와 이러한 불만도의 합을 최소로 하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 불만도의 합을 최소로 할 때, 그 불만도를 출력한다.

 

이 문제를 푸니 그리디가 뭔지 감이 잡힌듯 싶다.(다른 분 코드를 참조 해서 풀었지만...ㅎㅎ)

 

그리디가 아니면 이렇게 풀리가 없는데... 그리디니까...

package _2020_06_10.D;

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

public class Main {

	static int arr[];
	public static void main(String[] args) {
	  Scanner sc = new Scanner(System.in);	
	  int n = sc.nextInt();
	  
	  arr = new int[n];
	  for(int i = 0; i<n;i++) {
		  arr[i] = sc.nextInt();
	  }
	  
	  Arrays.sort(arr);
	  
	  long sum = 0;
	  for(int i = 1;i<=n;i++) {
		  sum += Math.abs(arr[i-1] - i);
	  }
	  
	  System.out.println(sum);
		
		

	}

}

 

여기서 그리디가 적용된 부분은

sum += 쪽이 그리디가 적용되었다.

 

생각해보면 1 부터 n까지 등수가 전부 다를 수 있고.. 동률도 있을 수 있고... 또.... 음... 굉장히 많다.

하지만 그리디로 적용하면 위같은 문제는 해결된다.

뭐 동률같은건 동석차 없이 라고 문제에서 명시 되었기 때문에 동률은 될리가 없다.

만약 된다면 그때 부터는 그리디 문제가 아니겠지...ㅎㅎ

 

아무튼...

이게 왜 가능하면 예상등수와 실제 등수를 뺏을때 최소가 되는 경우는

1등과 꼴지는 무조건적으로 결정하고 시작하는 방법이다.

왜냐하면 이 둘은 굉장히 편차가 크기 때문에 미리 제거 하는게 좋다고 생각한다.

 

하지만 두개만 생각하다보면 문제가 꼬일 수 있다.

 

그냥 오름 차순으로 정렬해보면 답이 쉽게 나온다.

오름 차순으로 정렬해보면 최소한의 경우가 나온다.

이게 무슨 말이냐면

1등 2등 3등 4등 5등 이 있다고 가정하면...

예상 등수가 이 밑에 들어간다.(물론 코드에는 예상 등수가 밑에 들어가지는 않는다.)

 

어차피 1등과 5등은 이미 정해졌기 때문에 논외로 생각하고...

 

이미 정렬되었기 때문에 최솟값을 구할 수 있다. 아까랑 챗바퀴 도는것 같은데...

아무튼 정렬하면 된다.... 

 

즉... 정렬 => 실제 등수..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int count = Integer.parseInt(bf.readLine());

        PriorityQueue<Integer> qu = new PriorityQueue<>();

        for(int i=0; i<count; i++) {
            int input = Integer.parseInt(bf.readLine());
            qu.add(input);
        }

        long angry = 0L;

        while (!qu.isEmpty()) {
            for(int i=1; i<=count; i++) {
                int poll = qu.poll();
                if(i < poll) {
                    angry = angry + (poll - i);
                } else {
                    angry = angry + (i - poll);
                }
            }
        }
        
        System.out.print(angry);

    }
}