SSAMKO의 개발 이야기

본 문제는 COCI(Croatian Open Competition in Informatics) 2009/2010 6라운드에 출제된 문제입니다. > COCI 2009/2010 6th Contest 1. 문제 카약 대회 진행중에 불행하게도 강한 바람으로 몇몇 카약이 손상되었다. 레이스 시작은 5분 밖에 남지 않았다. 불행 중 다행으로, 몇몇 팀들이 여분의 카약을 가져왔다. 카약은 무겁고 운반하기 힘들어서, 여분의 카약을 가져 온 팀들은 자신들의 경기 직전 혹은 경기 직후의 팀에게만 카약을 빌려줄 수 있다. 예를 들어, 레이스에 4번째로 참가하는 팀은 3번이나 5번 팀에게만 빌려줄 수 있다. 당연히 여분의 카약을 가져온 팀의 카약이 파손되었을 경우, 해당 팀은 당연히 자신들이 가져온 여분의 카약을 다른 팀에게..

그리디 알고리즘(greedy algorithm) - 동전 지불 문제¶ 그리디 알고리즘이란, 쉽게 말해 매 순간 최선의 선택을 하는 알고리즘이다. 전체의 최선이 아닌 매 순간의 최선이기 때문에 전체로 봤을 때는 최선이지 않은 경우가 종종 발생한다. 다시 말해 그리디 알고리즘에서는 2보 전진을 위한 1보 후퇴라는 말은 허용되지 않는다. 오로지 전진만 할 뿐이다. 그리디 알고리즘에 대해 좀 더 자세히 알고 싶다면, 나무위키 - 그리디 알고리즘을 참고하자 동전 지불 문제는 동전의 종류와 지불할 돈이 주어지면, 가장 적은 수의 동전을 사용해 비용을 지불하고, 그 때, 각 동전들이 몇 개 씩 사용되었는지, 잔돈이 생긴다면 잔돈까지 출력하는 코드를 짜는 것이다. 가장 큰 액수의 동전부터 사용해서 점차 작은 단위로 가..