들어가는 말
알고리즘 재활훈련 중인데 순수 구현이면서 생각보다 어려워서 재밌었던 실버 2 문제라 기록 남깁니다.
문제
https://www.acmicpc.net/problem/24913
접근
연산의 특징
질문(2번 연산)은 정후 씨의 당선 '가능성'만을 묻고 있습니다. 따라서 정후 씨보다 득표 수가 적은 후보들이 적당히 이 투표들을 나눠 받아서(분산 투표) 한 명이 지나치게 많은 표를 갖지 않도록 조절해야 합니다.
시간 복잡도 예측
최대 30만 번의 사건이 일어나고, 후보는 정후 씨를 제외하면 10만 명이나 됩니다. 정후 씨가 질문할 때마다 분산 투표를 한 뒤 최댓값을 구한다면 O(NQ)가 되어 시간이 모자랍니다. 따라서 O(N) 또는 O(Q)와 같은 선형 시간에 문제를 풀어야 함을 알 수 있습니다. 사건이 순서대로 일어나므로 이 문제는 O(Q)쪽이 맞겠네요.
아니면 우선순위 큐를 사용해야 하나? 라는 생각이 들 수 있습니다. 실제로 백준은 실버 상위 문제부터 우선순위 큐가 나오니까요. 우선순위 큐를 사용하면 후보들 중 가장 득표 수가 많은 사람을 O(log N) 시간에 뽑을 수 있습니다. 하지만 득표 수를 우선순위 큐에 넣는다면 집계(1번 연산)를 처리하기가 굉장히 까다롭다는 문제가 있어서 이 방법은 쓰기 어렵습니다.
풀이
집계
배열을 사용하면 쉽게 각 후보의 득표 수를 계산할 수 있습니다. 즉 집계는 우리가 크게 고려할 문제가 아닙니다.
질문
먼저 제일 쉬운 것부터 처리해 볼까요. 정후 씨가 x표를 추가로 얻어도 당선 가망조차 없을 수 있습니다. 만약 지금까지 집계된 표에서 다른 후보들 중 (정후 씨의 현재 득표 수 + x)표를 이미 얻은 사람이 있다면 말이죠. 이 경우에는 계산할 필요조차 없이 낙선입니다.
이 방법을 사용하기 위해서는 다른 후보들 중 가장 표를 많이 받은 사람의 득표 수를 알고 있어야 합니다. 이 값은 집계할 때 O(1) 시간으로 쉽게 구할 수 있습니다.
우리는 위에서 정후 씨가 x표를 받았음에도 낙선하는 경우를 걸렀습니다. 그러므로 여기까지 왔다는 것은 일단 y표를 분배하기 전에는 다른 모든 상대 후보들의 득표 수가 각각 정후 씨의 득표 수보단 적다는 뜻이겠죠. 여기서는 그림으로 생각하면 편했습니다.
초록색은 (정후 씨의 현재 득표 수 + x)표이며, 그림에서는 15표로 정했습니다.
보라색 세로줄은 각 후보의 현재 득표 수입니다. 다른 후보는 9명이고, 득표수를 배열로 나타내면 [0, 2, 3, 5, 5, 10, 11, 12, 13] 이 되겠네요. 정렬은 보기 편하라고 해놓았습니다.
여기서 다른 후보들에게 돌아갈 값인 y가 21이라고 한다면 어떻게 될까요? 마치 길가의 패인 부분이 먼저 물웅덩이가 되듯이 득표 수가 낮은 후보들부터 채워나가는 게 정후 씨의 1등을 유지하는 데 제일 안정적입니다. 아래 그림에서 어두운 부분 한 칸이 다른 후보들에게 돌아갈 한 표입니다.
이렇게 득표 수가 낮은 후보들에게 표를 적절하게 분배하면 최고 득표 수는 여전히 정후 씨의 득표 수보다 낮아서 당선에 영향을 주지 않습니다.
그러면 여기서 우리는 이 그림을 어떻게 코드로 만들 수 있을지 고민해 봐야 합니다. 먼저 검은 영역은 어디까지 가능할까요?
두 그림 중 위쪽은 되고, 아래쪽은 안 됩니다. 그러면 '되는 그림'을 다시 한번 보겠습니다.
합쳐놓으니 뭔가 보이시나요? 저는 네모가 보입니다.
결국 이 문제는 도형의 넓이 문제였습니다. 보라 영역과 검은 영역을 더했을 때, 가로가 N이고 세로가 정후 씨의 현재 득표 수 + x - 1인 직사각형의 넓이보다 큰지를 묻는 것이었죠.
검은 영역은 2번 연산의 y값으로 들어옵니다. 우리가 할 일은 매 사건 이후 보라 영역의 넓이를 기억하는 것이고, 이건 1번 연산에서 정후 씨가 아닌 다른 후보자가 받는 표들을 더하면 됩니다.
참고용 코드
자바스크립트입니다.
const [[candidateCount], ...events] = require('fs')
.readFileSync(0, 'utf-8')
.toString()
.trim()
.split('\n')
.map((line) => line.split(' ').map(Number));
const votes = new Array(candidateCount + 1).fill(0);
let myVote = 0;
let maxVote = 0;
let voteSum = 0;
const sol = [];
events.forEach(([type, x, y]) => {
switch (type) {
case 1: {
const isMe = y === candidateCount + 1;
if (isMe) {
myVote += x;
} else {
votes[y] += x;
voteSum += x;
maxVote = Math.max(maxVote, votes[y]);
}
break;
}
case 2: {
const hasTooStrongCandidate = myVote + x <= maxVote;
if (hasTooStrongCandidate) {
sol.push('NO');
break;
}
const canWin = voteSum + y <= (myVote + x - 1) * candidateCount;
sol.push(canWin ? 'YES' : 'NO');
break;
}
default:
}
});
console.log(sol.join('\n'));