정의

현재 상황에서 지금 당장 좋은 것만 고르는 방법이며, 그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

그리디 알고리즘의 유형은 다른 알고리즘 유형과 비교했을 때 사전에 외우지 않아도 풀 수 있을 가능성이 높은 알고리즘이라는 특징이 있다.

하지만 암기를 통해서 잘 할수 있는 유형도 아니다. 다양한 유형이 존재하므로 연습을 통해 훈련을 해야 한다.

예시

동전 거슬러주기

n = 1350
count = 0

coins = [500, 100, 50, 10]

for coin in coins:
	count += n // coin
	n %= coin

return count

간단한 예시를 들어보았다. 이는 화폐의 종류만큼 반복하므로 화폐의 종류가 K개라고 하면 O(K)의 시간 복잡도를 가지고 있다고 할 수 있다.

이렇게 간단한 예시가 나올 수 있는 이유는 가격이 높은 동전들은 가격이 낮은 동전들의 배수이기 때문이다.

예를 들어, 동전의 종류가 [500, 400, 100, 50] 이고 800원을 거슬러준다고 해보자.

그러면 Greedy방식으로는 500 + 100 + 100 + 100, 4개의 동전이라는 케이스가 존재하지만, 실제로 최소 케이스는 400 + 400이다.

그러므로 그리디 알고리즘은 이러한 최소한 아이디어를 떠올리고 이것이 정당한지를 판단해야 답을 도출할 수 있다.

큰 수의 법칙

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 같은 수는 연속으로 최대 K번까지 더할 수 있다. 단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 수라고 가정한다.
배열이 2, 4, 5, 4, 6이고 M이 8, K가 3이라고 할 때 최대합은 6+6+6+5+6+6+6+5=46이 될 것이다.

입력 조건

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

출력 조건

• 합을 출력한다.

Version 1

n, m, k = map(int, input().split())
li = list(map(int, input().split()))

cnt = 0
inner_cnt = 0
sum = 0

li.sort(reverse=True)

while (cnt < m):
    if inner_cnt == k:
       sum += li[1]
       inner_cnt = 0
    else:
        sum += li[0]
        inner_cnt += 1
    cnt += 1

이 문제는 M이 10,000 이하이므로 이 방식으로도 충분히 통과가 가능한데, M의 크기가 더욱 커진다면 시간 초과가 나올 것이다. 그러므로 수학적으로 해결할 수 있는 다른 방법을 알아보도록 하자.

Version 2

n, m, k = map(int, input().split())
li = list(map(int, input().split()))

li.sort()
first = li[n - 1]
second = li[n - 2]

count = int(m / (k + 1)) * k
count += m % (k + 1)

result = 0
result += (count) * first
result += (m - count) * second

return result

이 방식은 반복문으로 각 숫자를 매 turn마다 더해주는 방식이 아니라 반복되는 수열의 특징을 추출한 것이다. 배열이 2, 4, 5, 4, 6이고 M이 8, K가 3이라고 할 때의 예시를 다시 들어보자. 더해지는 수는 6+6+6+5+6+6+6+5 = 46으로 6+6+6+5가 반복되는 형태라고 할 수 있다. 이 값은 m / (k + 1) * k라고 할 수 있다. 나머지는 m % (k + 1)로 계산할 수 있을 것이다.