이것이취업을위한코딩테스트다_ch03.그리디_3-2 큰 수의 법칙.py

문제 설명

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

예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때, M이 8이고 k가 3이라고 가정하자.

이 경우 특정한 인덱스의 수가 연속해서 3번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과를 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5 = 46이 된다. 단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다.

예를 들어 순서대로 3, 4, 3, 4, 3으로 이루어진 배열이 있을 때 M이 7이고 k가 2라고 가정하자. 이 경우 두 번째 원소에 해당하는 4와 네 번째 원소에 해당하는 4를 번갈아 두 번씩 더하는 것이 가능하다.

결과적으로 4 + 4 + 4 + 4 + 4 + 4 + 4 = 28이 도출된다.

count = int(m / (k + 1)) * k
총 m개의 숫자를 더하는데 큰 수가 k번 더해지는게 몇 바퀴인지 구하고 
몫만큼 k번 큰수가 더해질 수 있으니깐 * k를 한다.

정답 풀이

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

data.sort()
first = data[n-1] # 가장 큰 수
second = data[n-2] # 두번째로 큰 수

# 가장 큰 수가 더해지는 횟수 계산
count = int(m / (k+1)) * k
count+ = m % (k+1)

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

print(result)