[이것이 코딩 테스트다, 그리디] 큰 수의 법칙

1. 문제 정의

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

• 입력: 첫째 줄에 N(2이상 1000이하), M(1이상 10000이하), K(1이상 10000이하)가 주어진다. 둘째 줄에는 N개의 자연수(1이상 10000이하)가 주어진다. 이때 입력으로 주어지는 K는 항상 M 이하다.
• 출력: 큰 수의 법칙에 따라 더해진 답을 출력한다.

2. 풀이

# 입력
n, m, k = map(int, input().split())
num_list = list(map(int, input().split()))

# 첫 번째로 큰 수와 두 번째로 큰 수 뽑아냄
max_num = max(num_list)
num_list.remove(max_num)
second_max_num = max(num_list)

# 그리디 알고리즘으로 계산
recurring_term = max_num * k + second_max_num
result = m//(k+1)*recurring_term + m%(k+1)*max_num

print(result)