[백준] 33705. 마스코트 정하기

newbieski·2025년 5월 2일
0

백준

목록 보기
245/246

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

문제요약

  • 1 ~ N 명이 사람이 마스코트에 투표를 함
  • 최소 한명은 1번에 투표를 함
  • 과반 이상이면 득표하면 뽑힘
  • 1번 마스코트를 뽑히게 하고 싶음.
  • l~r을 쫓아낼 수 있음
  • 최소 몇 번 쫓아내야 뽑힐까?

접근법

  • 1번 투표한 사람의 왼쪽, 오른쪽을 쫓아내면 1번이 뽑힘 => 즉 2번을 하면 무조건 뽑힘
  • 쫓아내지 않아도 이미 과반이면 1번이 뽑힘 => 0번도 가능
  • 그럼 이제 언제 1번인지를 판단하면 됨
  • 2번을 쫒아낼때 왼쪽만 쫓아내서 가능? 또는 오른쪽만 쫓아내서 가능? 한지를 판단함.
  • 그런데 끝에서부터 쫓아내지 않고 중간을 쫒아내서 가능한 경우가 있다면?
    • 중간의 왼쪽이든 오른쪽이든 1의 개수가 과반보다 많을 것임 => 둘 다 과반을 못넘으면 전체도 과반을 못 넘음
    • 과반을 넘는 쪽만 넘겨도 결과는 같으니까 끝에서부터 쫒아내도 됨
profile
newbieski

0개의 댓글