당장 좋은 것만 선택하는 Greedy

거스름돈 예제

 

손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야할 돈 N은 항상 10의 배수이다. 

 

    

--------------------------------------

화폐의 종류만큼 반복을 수행해야 한다. 따라서 화폐의 종류가 K개라고 할 때 위 소스코드의 시간 복잡도는 O(K)이다. 거슬러 줘야하는 돈 N은 시간 복잡도와 무관하다는 것을 할 수 있다. 

 

큰 수의 법칙

 

n개의 배열에서 주어진 수들을 m번 더하여 가장 큰 수를 만든다. 이때 특정 인덱스에 해당하는 수가 연속해서 k번까지만 더해질 수 있다. n, m k와 배열을 입력받았을 때 가장 큰 수를 출력하도록 만드시오.

--------------------------------------

숫자 카드 게임

숫자가 쓰인 카드들이 n행 * m열 형태로 놓여있다. 먼저 뽑고자 하는 카드가 포함된 행을 선택한다. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 

 

-------------------------------------

1이 될 때까지

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 수행하려 한다.

1. N에서 1을 뺀다.

2. N을 K로 나눈다. 

N과 K가 주어질 때, N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하시오