PC/UVa ID : 110108/10142

사설

개인적으로 책에 적혀있는 문제가 이해가 되지 않았다, 도데체 무슨 말을 하는지 몰라, 친구(박형준)과 토론을 하며 문제를 생각했고, 형준이가 문제에 대해서 이해하여, 여기에 정리하게 된다.

답지를 보고, 형준이가 말한 문제가 올바른지 검증을 했으므로, 이 문제가 100% 정확하다. 책의 문제가 이해가 되지 않아, 검색하다 이 블로그를 찾게 된 사람들에게 도움이 되었으면 한다.

개요

호주식 투표 제도를 구현하는 문제입니다. 호주식 투표 제도는 다음과 같은 알고리즘에 따라 후보자가 당선됩니다.

  1. 투표권자는 모든 후보자에게 순위를 메겨 투표를 합니다.
  2. 이때 1순위 후보자만을 집계하여, 과반수 이상 표를 얻은 사람이 있다면, 당선을 시킵니다.
  3. 만약 당선자가 없다면, 제일 표를 못 받은 후보자(복수 가능)를 탈락 시킵니다.
  4. 탈락된 후보자를 최 상위 순위로 찍은 투표용지들 중 그 다음 순위자로 표기된 자가 있다면, 그 순위자에게 표를 줍니다.
  5. 그리고 다시 집계하여, 과반수 이상 표를 얻은 사람이 있다면, 당선을 시키고 당선된 사람이 없다면, 3번의 처리과정을 반복하게 됩니다.

입력

  1. 처리하고자 하는 투표 케이스(대통령 선거, 학급반장선거 등을 동시에 진행할 경우, 2 케이스 이다.) 의 갯수를 의미하는 양의 정수를 1개 입력 받는다.
  2. 그 다음 빈줄이 하나 들어 간다.
  3. 그리고 투표 케이스 중 첫번째 케이스의 후보자를 수를 양의 정수 1개로 입력받는다. - 예외 : 20명 이하
  4. 그리고 그 후보자 수 만큼 이름을 입력 받는다. - 예외 : 80자 이하
  5. 그리고 이름 출력
  6. 그리고 투표용지를 받는다 - 예외 : 장수는 1000장 이하로 받는다.
  7. 그리고 빈줄을 입력하면(그냥 엔터만) 투표 결과를 출력한다.

출력

  1. 당선된 후보자가 있다면 이름을 출력한다.
  2. 이때 다른 케이스의 투표도 있다면, 빈줄 한개를 출력하고, 다시 입력받고 반복한다.


입력과 출력의 예

http://books.google.co.kr/books?id=lcnSCDcDocMC&pg=PA25&lpg=PA25&dq=110108+10142&source=bl&ots=tMLKzbDL8O&sig=emx4BRw-AM1aFvc0l6hS18IwRJw&hl=ko&ei=gwvtSvD4BZqW6wOJ_tnvCw&sa=X&oi=book_result&ct=result&resnum=1&ved=0CAgQ6AEwAA#v=onepage&q=110108%2010142&f=false

풀이



예외적으로 최대 취득수와 최소 취득수가 같다면, 누구를 탈락 시킬지 정할 수 없기 때문에, 재투표를 하게 한다.이로서 챕터 1이 끝났다. 챕터 2, 자료 구조로 넘어간다.


posted by 농사를 짓는 게임 프로그래머 최익필

댓글을 달아 주세요

  1. Favicon of https://www.ikpil.com 농사를 짓는 게임 프로그래머 최익필 2009.11.01 17:19 신고  Addr  Edit/Del  Reply

    이 문제로 깨달은 것은, 정확한 프로그램을 만드는 것이다.
    얼마나 문제를 정확하게 알고 있느냐,

    이것이 보다 정확한 프로그램을 만드는 방법이다.