BOJ - 2012 등수 매기기

Problem

---

Solve

등수의 불만도를 최소화 하기 위해서는 각 예상등수를 오름차순 정렬하여 최대한 예상등수와 등수와의 차이를 줄여야한다.

예상 등수를 오름차순하여 grade를 1부터 비교하며 불만도의 합을 구하는 것이다.

이때 각 등수의 불만도는 최대 1000000, 학생의 수는 500000이므로 1000000*500000은 long타입을 사용해야한다.

---

Code

public class 등수매기기 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());

		//예상 등수
		int[] anticipateGrade = new int[N];

		for(int i=0;i<N;i++){
			anticipateGrade[i] = Integer.parseInt(br.readLine());
		}

		//예상 등수 오름차순 정렬
		Arrays.sort(anticipateGrade);

		long answer=0;
		int grade=1;
		for(int i=0;i<N;i++){
        	//예상등수 - 등수의 차이로 최소 불만도의 합 구하기
			answer += Math.abs(anticipateGrade[i]-grade);
			grade++;
		}

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}
}

---

Result

---

Reference