Greedy 알고리즘

그리디 알고리즘은 탐욕법이라고도 말하며,
현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.
일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.

그리디 해법은 그 정당성 분석이 중요하다.
→ 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토해야 한다.

일반적인 상황에서 그리디는 최적의 해를 보장할 수 없을 때가 많다.
하지만 코테에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서,
이를 추론할 수 있어야 풀리도록 출제가 된다.

그리디에서 큰 단위가 항상 작은 단위의 배수인 경우에는 최적의 해를 빠르게 찾을수 있는데, 만약 큰 단위가 작은 단위의 배수가 아닌 경우 (500, 400, 100 에서 800원을 거슬러 주는 경우)는 최적의 해가 될 수 없다.

결론적으로 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 한다.

장점은 화폐의 종류가 K라고 하면, O(K) 시간 복잡도를 가진다.
금액 자체와는 무관하며, 동전의 총 종류에만 영향을 받는다.

간단한 예제를 보자.

큰 수의 법칙 :
예를 들어 순서대로 2, 4, 5, 4, 6으로 이뤄진 배열이 있을 때,
M = 8 K = 2라고 하자.
이 경우 특정한 index의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5인 46이 된다.
참고로 3, 4, 3, 4 배열이 있다면 두 번째의 4와 네 번째의 4는 따로따로 취급한다.
즉 4 + 4 + 4 + 4…가 가능하다고 한다.
배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 큰 수의 법칙에 따른 결과를 출력하라.

입력 예) 5 8 3 2 4 5 4 6

출력 예) 46

N, M, K = map(int, input().split())
data = list(map(int, input().split()))

data.sort()
first = data[N-1]
second = data[N-2]

result = 0

while True:
    for i in range(K):
        if M == 0:
            break
        result += first
        M -= 1
    if M == 0:
        break
    result += second
    M -= 1

print(result)

우선 N, M, K를 map을 이용하여 연속적으로 입력을 받고 배열을 list, map을 이용하여 한번에 입력 받는다.
그런 다음 정렬을 하여 가장 뒷 부분과 두 번째 뒷 부분의 원소를 first, second로 정의한다. (가장 큰 2개)
문제에서 이 포인트가 굉장히 중요 하였다. 중요한 것은 가장 큰 두개만 있으면 해결이 되기 때문이다.

그런 다음, while 문을 통해 무한 loop를 걸어주고, for문을 통하여 K(한 원소가 반복하는 횟수)의 범위만큼 가장 큰 수를 더해준다.
그러다가 K의 범위를 벗어나면 두번째로 큰 수를 더해주고 다시 for문으로 들어가게 된다.
한번 연산을 할 때마다 M을 감소시켜주어 M == 0이 되는 순간에 break를 통해 빠져나가 결과를 출력하게 된다.