[BOJ 24913 // C++] 개표

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 24913번 문제인 개표이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/24913 

24913번: 개표

문제가 요구하는 바를 제대로 이해하는 것이 중요한 문제이다.

2 x y: 정후가 묻는다. "지금까지 집계된 표 이후 저를 찍은 표가 x 장, 제가 아닌 후보를 찍은 표가 y 장 더 집계된다면 제가 당선될 가능성이 있나요?"

위의 지문에서 제가 아닌 후보를 찍은 표는 1번 쿼리와 같이 정후가 아닌 한 후보에게 돌아가는 표가 아닌, 정후를 제외한 다른 후보를 찍은 모든 표를 의미한다. 또한, 제가 당선될 가능성이 있다는 것은 y장의 제가 아닌 후보를 찍은 표가 정후가 아닌 후보에게 잘 돌아가서 정후가 단독 1등이 되는 경우가 존재한다는 의미이다.

 

정후가 당선될 가능성이 존재하려면 정후를 제외한 나머지 모든 후보가 정후보다 적은 표를 받은 경우가 있는지를 살펴야 한다. 이는, 1) 정후가 받은 표와 같거나 더 많은 표를 받은 후보가 전혀 없으며, 2) 다른 후보가 받은 모든 표의 개수가 "정후가 받은 표의 개수 - 1" * N 이하인지를 확인하는 것으로 빠르게 확인할 수 있다. 정후를 제외한 가장 많은 표를 받은 후보의 표수나 다른 후보가 받은 모든 표의 개수는 표에 대한 정보가 들어올 때마다 간단히 갱신해나갈 수 있기 때문이다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

ll vote[100002];
ll mx = 0;
ll total = 0;

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

	int N, Q; cin >> N >> Q;
	while (Q--) {
		int q, x, y; cin >> q >> x >> y;
		if (q == 1) {
			ll& v = vote[y];
			v += x;
			if (y <= N) {
				total += x;
				mx = max(mx, v);
			}
		}
		else {
			if (vote[N + 1] + x > mx && (vote[N + 1] + x - 1) * N >= total + y ) cout << "YES\n";
			else cout << "NO\n";
		}
	}
}