[C++] 백준 16678번: 모독

문제 링크

16678번: 모독

문제 요약

프로젝트 Defile을 실시하면 다음의 절차가 실행된다.
(1) 모든 국회의원을 모독해서 각각의 명예 점수를 1씩 감소시킨다.
(2) (1)로 인해 1명이라도 국회의원에서 박탈당한 사람이 발생했다면 국민들의 분노를 이용해 (1)로 돌아간다.
(3)에 의해 국회의원에서 박탈당한 사람이 없다면 프로젝트를 종료한다.
왕은 국회의원들을 모두 자격을 박탈시키고자 하지만 명예를 지키기 위해 한 번만 Defile을 실시한다. 이때, 한 번으로도 Defile을 마칠 수 있도록, 국회의원 중 일부의 명예 점수를 해커를 고용해 감소시키고자 한다. 해커는 국회의원 1명의 명예 점수를 1점 감소시킬 수 있다. 왕이 고용해야하는 해커의 수의 최솟값을 출력해야 한다.

접근 방법

문제에서 제공되는 TC가 함정인 문제입니다. 예전에도 TC대로 접근했다가 한 번 당한적이 있었는데, 이번에도 당하고 말았습니다.

먼저 오름차순으로 명예 점수들을 정렬한 뒤에, 처리를 해야 합니다. 현재 감소된 명예 점수의 합을 저장할 변수를 하나 선언합니다. 이 변수를 score라고 호칭하겠습니다. 정렬한 점수들을 순서대로 접근하면서, 현재 명예 점수와 score를 비교합니다. 현재 명예 점수가 score보다 작거나 같으면 continue를 통해 무시해줍니다. 이 명예 점수는 자동적으로 배제된 명예 점수입니다.

그 외의 경우에는 score를 1 증가시킵니다. 그럼에도 score가 현재 명예 점수보다 작으면 결과에 둘의 차를 더해주면 됩니다. 그러면 그 국회의원은 자격이 박탈되어 문제에서 명시된 1번 절차로 돌아갈 수 있습니다.

TC 밑에 적힌 문구를 보고 생각하면 헤매기 쉬울 것 같습니다.

코드

#include <bits/stdc++.h>

using namespace std;

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

	int n;
	cin >> n;

	vector<int> v(n);
	for (int i = 0; i < n; i++)
		cin >> v[i];

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

	int score = 0;
	long long ans = 0;
	for (auto& i : v) {
		if (i <= score)
			continue;
		
		score++;

		if (score < i)
			ans += i - score;
	}

	cout << ans << '\n';
	return 0;
}