<div>먼저 이건 절대로 과제가 아님을 밝힙니다.</div> <div> </div> <div>(전 아직 대학생도 아니거든요;;;)</div> <div> </div> <div>효율적인 프로그램을 짜는 방법에 대해 생각해 볼 수 있는 좋은 문제인것 같아서 가져와 봤어요... ㅋ</div> <div> </div> <div>그럼 문제 나갑니다!</div> <div>------------------------</div> <div> </div> <div><font size="5"><strong>컬러볼</strong></font></div> <div>지훈이가 최근에 즐기는 컴퓨터 게임이 있다. 이 게임은 여러 플레이어가 참여하며, 각 플레이어는 특정한 색과 크기를 가진 자기 공 하나를 조정하여 게임에 참여한다. 각 플레이어의 목표는 <strong>자기 공보다 크기가 작고 색이 다른 공 </strong>을 사로잡아 그 공의 크기만큼의 점수를 얻는 것이다. 그리고 다른 공을 사로잡은 이후에도 본인의 공의 색과 크기는 변하지 않는다. 다음 예에는 네 개의 공이 있다. 편의상 색은 숫자로 표현한다.</div> <div style="text-align:left;"><img width="0" height="0" style="border:;" alt="컬러볼.png" src="http://thimg.todayhumor.co.kr/upfile/201505/1433060166dHXzUbyjE4mtXB7l5bpc5aJiu6CpI.png"></div> <div align="center"><br></div> <div style="text-align:left;"> <table width="100%" style="border-style:solid;border-collapse:collapse;" border="1" cellspacing="0" cellpadding="3"><tbody><tr><td width="50" height="25"> <div align="center"> 공 번호</div></td> <td width="50"> <div align="center"> 색</div></td> <td width="50"> <div align="center"> 크기</div></td></tr><tr><td> <div align="center"> 1</div></td> <td> <div align="center"> 1</div></td> <td> <div align="center"> 10</div></td></tr><tr><td> <div align="center"> 2</div></td> <td> <div align="center"> 3</div></td> <td> <div align="center"> 15</div></td></tr><tr><td> <div align="center"> 3</div></td> <td> <div align="center"> 1</div></td> <td> <div align="center"> 3</div></td></tr><tr><td> <div align="center"> 4</div></td> <td> <div align="center"> 4</div></td> <td> <div align="center"> 8</div></td></tr></tbody></table></div> <div style="text-align:left;"><img width="0" height="0" style="border:;" alt="컬러볼.png" src="http://thimg.todayhumor.co.kr/upfile/201505/14330601783NeQFRqdzh.png"></div> <div><br>이 경우, 2번 공은 다른 모든 공을 사로잡을 수 있다. 반면 1번 공은 크기가 더 큰 2번 공과 색이 같은 3번 공은 잡을 수 없으며, 단지 4번 공만 잡을 수 있다.</div> <div>공들의 색과 크기가 주어졌을 때, 각 플레이어가 사로잡을 수 있는 모든 공들의 크기의 합을 출력하는 프로그램을 작성하시오. 수행 시간은 1초를 넘을 수 없으며 사용하는 메모리는 128MB를 넘을 수 없다.</div> <div> </div> <div><strong><font size="4">입력 형식</font></strong></div> <div>표준 입력의 첫 술에는 공의 개수를 나타내는 자연수 N이 주어진다(1<=N<=200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1<=Ci<=N, 1<=Si<=2000). 서로 같은 크기 혹은 같은 색의 공들이 있을 수 있다.</div> <div> </div> <div><font size="4"><strong>출력 형식</strong></font></div> <div>표준 출력에 N개의 줄을 출력한다. N개의 줄 중 i번째 줄에는 i번째 공을 가진 플레이어가 잡을 수 있는 모든 공들의 크기 합을 출력한다.</div> <div> </div> <div><strong><font size="4">입력과 출력의 예</font></strong></div> <div><font size="2">입력(1)</font></div> <div><font size="2">4</font></div> <div><font size="2">1 10</font></div> <div><font size="2">3 15</font></div> <div><font size="2">1 3</font></div> <div><font size="2">4 8</font></div> <div> </div> <div>출력(1)</div> <div>8</div> <div>21</div> <div>0</div> <div>3</div> <div> </div> <div>입력(2)</div> <div>3</div> <div>2 3</div> <div>2 5</div> <div>2 4</div> <div> </div> <div>출력(2)</div> <div>0</div> <div>0</div> <div>0</div> <div>------------------------</div> <div>p.s)이 문제 읽자마자 '서로 2개씩 짝지어서 비교하면 되겠네' 하시는 분들!</div> <div> </div> <div>그렇게 프로그램 짜면 제한 시간 1초를 벗어나게 되요....</div>
출처 |
최근 있었던 프로그램 대회 문제인데요,
정확한 링크를 못걸겠네요..;; |
댓글 분란 또는 분쟁 때문에 전체 댓글이 블라인드 처리되었습니다.