https://www.acmicpc.net/problem/33705
문제요약
- 1 ~ N 명이 사람이 마스코트에 투표를 함
- 최소 한명은 1번에 투표를 함
- 과반 이상이면 득표하면 뽑힘
- 1번 마스코트를 뽑히게 하고 싶음.
- l~r을 쫓아낼 수 있음
- 최소 몇 번 쫓아내야 뽑힐까?
접근법
- 1번 투표한 사람의 왼쪽, 오른쪽을 쫓아내면 1번이 뽑힘 => 즉 2번을 하면 무조건 뽑힘
- 쫓아내지 않아도 이미 과반이면 1번이 뽑힘 => 0번도 가능
- 그럼 이제 언제 1번인지를 판단하면 됨
- 2번을 쫒아낼때 왼쪽만 쫓아내서 가능? 또는 오른쪽만 쫓아내서 가능? 한지를 판단함.
- 그런데 끝에서부터 쫓아내지 않고 중간을 쫒아내서 가능한 경우가 있다면?
- 중간의 왼쪽이든 오른쪽이든 1의 개수가 과반보다 많을 것임 => 둘 다 과반을 못넘으면 전체도 과반을 못 넘음
- 과반을 넘는 쪽만 넘겨도 결과는 같으니까 끝에서부터 쫒아내도 됨
newbieski