코테_Chapter01_그리디

그리디 알고리즘은 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 여기서 탐욕적이라는 말은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다.

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로','가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다. 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다.

 

거스름돈

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈을 사용할 500원, 1000원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

풀이

'가장 큰 화폐 단위로부터' 돈을 거슬러 주는 것이다. N원을 거슬러 줘야 할 때, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 준다. 그다음 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 최소의 동전 개수로 모두 거슬러 줄 수 있다.

# 당신은 음식점의 계산을 도와주는 점원이다.
# 카운터에는 거스름돈을 사용할 500원, 1000원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다.
# 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라.
# 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

N = int(input())

coin_type = [500, 100, 50, 10]
cnt = 0

for coin in coin_type:
    cnt += N//coin
    N %= coin

print(cnt)

 

그리디 알고리즘의 정당성

대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없을 가능성이 다분하다. 하지만 거스름돈 문제에서 '가장 큰 화폐 단위부터'돈을 거슬러 주는 것과 같이, 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때는 매우 효과적이고 직관적이다.

그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다. 거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.

 

큰 수의 법칙

큰 수의 법치은 다야한 수로 이루어진 배열이 있을 떄 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.

 

예시

입력조건

• 첫째 줄에 N(2<= N <= 1,000), M(1<= M <= 10,000), K(1<=K<=10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
• 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1이상 10,000 이하의 수로 주어진다.
• 입력으로 주어지는 K는 항상 M보다 작거나 같다.

출력 조건

• 첫째 줄에 동빈이의 큰 수의 법치에 따라 더해진 답을 출력한다.

풀이

N, M, K = map(int, input().split())
lst = list(map(int, input().split()))
res, cnt = 0, 0
lst.sort()

# #시간복잡도 O(n)
# for i in range(M):
#     if cnt <= K:
#         res += lst[-1]
#         cnt += 1
#     else:
#         res += lst[-2]
#         cnt = 0

# # 시간복잡도 O(1)
# cnt = M//(K+1) * K
# cnt += M % (K+1)

# res += cnt*lst[-1]
# res += (M-cnt)*lst[-2]

print(res)