큰 수의 법칙 (python)

문제

첫째 줄에 N M K 가 주어지고 둘째 줄에 N개의 자연수가 주어진다.

N개의 자연수 배열중 M개로 만들 수 있는 가장 큰 수를 만들어서 출력하라 각 배열의 값은 반복 가능하고

같은 인덱스는 K번 초과해서 연속해서 나오면 안 된다 같은 수라도 인덱스가 다르면 연속하여 놓을 수 있다

예를 들어 3, 4, 3, 4, 3 이면 인덱스 1번과 3번은 다른 수이므로 정답은 4 * M가 될 것이다.

풀이 방법

배열을 정렬을 해서 가장 큰 수와 두번째로 큰 수를 결정한다 만약 가장 큰 수가 2개 이상이어도 상관없이 진행

그런 후 가장 큰 수를 만드는 패턴을 보면 K개의 가장 큰 수가 연속해서 나오고 두번 째로 큰 수가 한 번 나오고

다시 가장 큰 수가 k번 나오는 식으로 반복 되야 가장 큰 수를 만들 수 있다.

그러므로 가장 큰 수가 더해지는 횟수는 M / (k+1) * k + M % (k + 1) 이 된다. M % (k + 1)은 나누어 떨어지지 않을 때

남은 부분은 가장 큰 수로 채워주면 되기 때문이다 

그럼 M에서 큰 수가 더해지는 횟수를 빼면 두번 째로 큰 수가 더해지는 횟수가 된다

 

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

data.sort()
max_num = data[n-1]
second_num = data[n-2]

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

ans = count * max_num + (m - count) * second_num
print(ans)