큰 수의 법칙_이코테 실전문제 [ 그리디]

큰 수의 법칙

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

입력 조건

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

출력 조건

• 첫째 줄에 동빈이의 큰 수의 법칙에 따라 더해진 답을 출력한다.

풀이

1. 입력받은 N개의 자연수를 정렬한다.
2. 가장 큰 수를 K번 더한다.
3. 두번째로 큰 수를 한번 더한다.
4. 2번과 3번 과정을 더하는 횟수가 M번 될때까지 반복한다.

예시 코드

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

N, M, K = map(int, input().split())
result = 0
num = list(map(int, input().split()))
num.sort(reverse=True)
for i in range(M):
    for j in range(K):
        if M == 0 : break
        result += num[0]
        M -= 1
    if M == 0 : break
    result += num[1]
    M -= 1
    
print(result)