(백준 1417 국회의원 선거

• tags : (algorithm

  No matching post could be found

• 문제 링크 : https://www.acmicpc.net/problem/1417
• 풀이 링크
  • Python
  • Go
  • Node.js

• 우선순위 큐를 사용하면 더욱 쉽게 해결할 수 있을 것 같은데, Python을 제외한 언어로 풀어보기 위해 그리디하게 접근했다.

• 기본적인 구조는 다음과 같다.
• 표는 최대 100표이므로, 101 길이 리스트를 만들어서 각 표를 받는 후보의 수를 기록한다.
• 이후 다솜이가 받은 표가 최대가 될 때까지, 다른 후보의 표를 1개씩 가져간다.

votes = [0] * 101
for _ in range(N - 1):
    v = II()
    votes[v] += 1

• 101길이 배열에서 특정 표를 받은 후보들 만큼 표시한다.

for i in range(100, 0, -1):
    if not votes[i]:
        continue
    while votes[i]:
        if dasom > i:
            break
        dasom += 1
        votes[i] -= 1
        votes[i - 1] += 1
        answer += 1
    if (not votes[i] and dasom >= i) or dasom > i:
        break

• 100표부터 1표까지 순서대로 확인한다.
  • 만약 해당 표만큼 받은 사람이 없다면 넘어간다.
  • 아니라면 1표씩 다솜이의 표로 옮기는 과정을 하는데,
    • i표 만큼 얻은 사람이 1명 줄면 i-1표를 얻은 사람을 늘리고,
    • 정답으로 하나 더한다.
• 다솜이의 표가 지속적으로 변하기 때문에 for문의 마지막마다 다솜이의 표를 확인하여 마무리한다.

dasom++
votes[i]--
votes[i-1]++
answer++

• 전체적인 코드는 같은데, +=1 대신 ++연산으로 대체할 수 있는 부분 말고 거의 같다.