[PS] 백준 #2012. 등수 매기기

문제 정보

• 난이도: 실버 III
• 문제 주소: https://www.acmicpc.net/problem/2012
• 이 문제를 푼 이유: 그룹 연습 Div.2

 

문제

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

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

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

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

 

나의 풀이

첫 시도에는 n만큼의 배열에 모두 0을 저장해두고, 입력한 숫자를 인덱스로 가지는 항을 +1이 되도록 구현했다. 배열에서 값이 1 초과인 항, 즉 중복항들을 골라서 값이 0인 항들과의 인덱스를 빼주는 식으로 계산했다. 그랬더니 45% 지점에서 런타임 에러 (Out of bound)가 발생했다. 

이를 해결하기 위하여 필기를 하다가, 단순히 입력된 값과 현재 인덱스의 위치 차이를 모두 더해도 어차피 순서만 바뀌는 것이니 똑같다는 것을 깨닫게 되었다. 최악의 경우 모두 50만을 작성하면 숫자가 1억을 훨씬 넘어가므로 long long 자료형으로 |입력된 값 - 인덱스|를 모두 더하니 정답 처리되었다.

#include <bits/stdc++.h>

using namespace std;

// 1차 시도: 45%에서 런타임 에러 (Out of bound)

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n; cin >> n;
	vector<int> rank;

	for (int i = 0; i < n; i++) {
		int myRank; cin >> myRank;
		rank.push_back(myRank);
	}

	sort(rank.begin(), rank.end());

	long long result = 0;

	for (int i = 0; i < n; i++) {
		result += (long long) abs(rank[i] - i - 1);
	}

	cout << result;
}