Problem

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙.
단 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다.
예를 들어 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때, M이 8이고, K가 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 => 28

입력 조건

• 첫째 줄어 N(2 <= N <= 1000), M( 1 <= M <= 10,000), K(1 <= K <= 10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
• 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10,000이하의 수로 주어진다.
• 입력으로 주어지는 K는 항상 M보다 작거나 같다.

My Code

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

sum = 0
count = 0 #제일 큰 수를 더한 횟수 카운터

while count < m:
    for i in range(k) :
        sum += data[0]
        count += 1
    sum += data[1]
    count += 1

print(sum)

Review

처음에 생각했던 아이디어는

가장 큰 수를 k번 더하고 두번째로 큰 수를 1번 더하는 것을 m번 반복하자

였다. 이것을 토대로 위의 코드를 짰다.

하지만 만약 k값이나 m값이 커지는 경우 실행 시간이 늘어날 수 있다. 이를 방지하기 위해서는 가장 큰 수가 더해지는 횟수를 구해서 그 횟수만큼 곱해주는 것이 알고리즘에 도움이 된다.

가장 큰 수가 더해지는 횟수
int(M/(K+1))*K+M%(K+1)