그리디알고리즘

[ 문제 ] 춘향이는 편의점 카운터에서 일한다. 손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오. 예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다. [ 코드 ] 1. 내 코드 StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput())); StreamWri..

[ 문제 ] $N$장의 카드가 좌우 일렬로 놓여있다. 각 카드에는 하나의 정수가 적혀있는데, 왼쪽에서 i번째 카드에 적혀있는 정수는 A_i다. (1 ≤ i ≤ N) 여러분은 N장의 카드 중 몇 장을 골라 제거할 수 있다. 이때, 제거되지 않은 카드의 순서는 유지된다. 예를 들어, N = 5, A = [3, 1, 4, 1, 5]라고 하자. 여러분이 두 번째와 다섯 번째 카드를 제거한다면, 남은 카드들에 적혀있는 수들은 왼쪽부터 차례대로 3,4,1이 된다. 즉, 남은 카드들 중 왼쪽에서 세 번째 카드에 적혀있는 수는 1이 된다. 몇 장의 카드를 골라 제거한 후, 남은 카드들 중 왼쪽에서 x번째 카드에 적혀있는 수가 정확히 x라면, 그 카드를 제자리 카드라고 부르자. 모든 남은 카드가 제자리 카드라면, 제자리..

[ 문제 ] “반갑다. 내 이름은 반고흐#31555! 조선 최고의 활잡이지. 오늘도 난 금강산 위에서 적들을 노리고 있지. 내 앞에 있는 적들이라면 누구도 놓치지 않아! 좋아, 이제 곧 월식이 시작되는군. 월식이 시작되면 용이 적들을 집어삼킬 것이다. 잘 봐두어라! 마장동 활잡이 반고흐#31555님의 실력을-!” 반고흐#31555는 자기 뒤쪽 봉우리에 덩기#3958이 있음을 전혀 모르고 있었다. 덩기#3958도 반고흐#31555와 마찬가지로 월식이 시작되면 용을 불러내어 눈앞에 있는 다른 활잡이들을 모두 처치할 생각이다. 사실, 반고흐#31555와 덩기#3958 뿐만 아니라 금강 산맥의 N개 봉우리에 있는 모든 활잡이들이 같은 생각을 가지고 있다. 반고흐#31555가 있는 금강 산맥에는 총 N개의 봉우리..

[ 문제 ] 3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 각각 5분, 1분, 10초이다. 냉동음식마다 전자레인지로 요리해야할 시간 T가 초단위로 표시되어 있다. 우리는 A, B, C 3개의 버튼을 적절히 눌러서 그 시간의 합이 정확히 T초가 되도록 해야 한다. 단 버튼 A, B, C를 누른 횟수의 합은 항상 최소가 되어야 한다. 이것을 최소버튼 조작이라고 한다. 만일 요리시간이 100초라고 하면(T=100) B를 1번, C는 4번 누르면 된다. 이와 다르게 C를 10번 눌러도 100초가 되지만 이 경우 10번은 최소 횟수가 아니기 때문이 답이 될 수 ..