문제

주어진 배열에서의 수를 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 = 28

조건:

• 2 $\leq$ N $\leq$ 1,000
• 1 $\leq$ M $\leq$ 10,000
• 1 $\leq$ K $\leq$ 10,000

방법 1

• 제일 큰 두 수만 중요하다.
• 가장 큰 수를 K번 더하고, 두 번째로 큰 수를 한 번 더하기. (반복)

# N: 배열의 크기 
# M: 숫자가 더해지는 총 횟수 
# K: 연속해서 더해질 수 있는 횟수  

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

data.sort() 
first = data[n-1] 
second = data[n-2] 

result = 0 

while True: 
    for i in range(k): 
    	if m == 0: 
            break 
        result += first 
       	m -= 1 
    if m == 0: 
    	break 
    result += second 
    m -= 1 

print(result) 

하지만 M의 크기가 크다면 시간 초과 판정을 받게 된다

방법 2

• 반복되는 수열 (6, 6, 6, 5)
  • 수열의 길이는 K + 1 이다. (K = 3)
• M이 13이라면 (6, 6, 6, 5), (6, 6, 6, 5), (6, 6, 6, 5), (6)
  • 13 // 4 = 3
  • 13 % 4 = 1
• 총 합: (M // (K + 1)) * (FIRST * K + SECOND) + (M % (K + 1)) * FIRST
• 또 다른 풀이: 가장 큰 수가 더해지는 횟수를 구하고, M에서 빼서 두번째로 큰 수가 더해지는 횟수를 찾기
  • 가장 큰 수가 더해지는 횟수:COUNT = (M // (K + 1)) * K + (M % (K + 1))
  • 두 번째로 큰 수가 더해지는 횟수: M - COUNT
  • 총 합: count * FIRST + (M - count) * SECOND

# N: 배열의 크기 
# M: 숫자가 더해지는 총 횟수 
# K: 연속해서 더해질 수 있는 횟수  

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

data.sort() 
first = data[n-1] 
second = data[n-2] 

# 1번 
return (m // (k + 1)) * (first * k + second) + (m % (k + 1)) * first

# 2번 
count = (m // (k + 1)) * k + (m % (k + 1)) 
return count * first + (m - count) * second