본문 바로가기

TIL/코테 스터디

99클럽 코테 스터디 24일차 TIL: 최대 힙 + 그리디

반응형

문제

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

풀이

1번 기호가 나머지 기호보다 많은 투표수를 받도록 해주어야 한다.
최소 표를 구해야 한다.

나머지 후보들 중에서 가장 득표를 많이받은 후보의 표를 뺏어와야 하므로, 최대값을 뽑아야하는데
최대힙을 구현하면 빠르게 최대값을 구현할 수 있다.

최대힙에서 pop 연산을 하고, 뽑은 요소에 -1을 해주어 다시 최대 힙에 넣어주고
1번 기호의 표를 + 1 해준다.

이를 반복하며 1번 기호가 최대힙에서 뽑은 요소보다 득표수가 많다면 종료해주면 되는 문제

소스코드

후기

작곡 레슨이 있어서 빠르게 비기너 문제를 풀이했다. 쉽게 풀 수 있었던 문제

반응형