큰 수의 법칙

1. 문제

2. 풀이

처음에는 좀 헷갈렸는데, 계속 보다보니 이해가 됐다.

예를 들어 N, M, K가 각각 5, 20, 3이고 값이 2, 2, 2, 3, 4이면 44443 44443 44443 ... 이렇게 다섯 뭉탱이로 나눌 수 있다.
20을 (3+1)으로 나눈 몫만큼의 뭉탱이로 나눌 수 있는 것이다.

이때 이용하는 수가 두개 이하라는 것을 알 수 있는데, 왜냐하면 한개는 K번만큼 쓰이는 가장 큰 수이고 나머지 하나는 K가 아닌 중간에 있는 그 다음으로 큰 수 (혹은 같은 수)이기 때문이다. 세 번째 수는 없다.

# 파이썬 코드
N, M, K = map(int, input().split(" "))
array = list(map(int, input().split(" ")))
array.sort()

v1 = M//(K+1)*K * array[-1] # 큰 수가 반복되는 부분
v2 = (M - M//(K+1)*K) * array[-2] # 뭉탱이로 나뉘는 부분
res = v1 + v2

print(res)