[이코테] 동빈이의 큰 수의 법칙(그리디)

다양한 수로 이루어진 배열이 있을 때, 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없으며, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다. 배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 동빈이의 큰 수의 법칙에 따른 결과를 출력하시오.

#N, M, K를 공백을 기준으로 구분하여 입력 받기
n, m, k = map(int, input().split())
#N개의 수를 공백을 기준으로 구분하여 입력 받기
data = list(map(int, input().split()))

data.sort() # 입력 받은 수들 오름차순 정렬
first = data[n - 1] # 가장 큰 수(인덱스를 기준으로 0부터 시작하기 때문)
second = data[n - 2] # 두 번째로 큰 수(마찬가지)

#가장 큰 수가 더해지는 횟수 계산
count = int(m / (k + 1)) * k #반복되는 수열의 길이는 1부터 시작하기 때문에 k+1
count += m % (k + 1) #m을 (k+1)로 나눈 몫이 수열이 반복되는 횟수기 됨

result = 0
result += (count) * first # 가장 큰 수 더하기
result += (m - count) * second # 두 번째로 큰 수 더하기

print(result) # 최종 답안 출력

책에서는 while문을 이용해서 단순하게 출력하는 방법도 구현되어 있으나, M의 크기가 100억 이상이 된다면 시간 초과 판정을 받기 때문에 위와 같은 방법이 더 좋다.
핵심은 반복되는 수열을 파악해야 한다는 것, m % (k + 1)이