[Algorithm] 그리디 - 큰 수의 법칙

🔍 문제

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

입력 조건

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

출력 조건

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

입출력 예시

입력

5 8 3
2 4 5 4 6

출력

46

내 답안

첫 번째 답안

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

# N개의 자연수 입력받기
data = list(map(int, input().split()))
# 큰 수부터 내림차순 정렬하기
data.sort(reverse=True)

result = 0
count = 0

for i in range(m):
    if count == k:
        result += data[1]
        count = 0
    else:
        result += data[0]
        count += 1

print(result)

두 번째 답안

## N, M, K 입력받기
n, m, k = map(int, input().split())

# N개의 자연수 입력받기
data = list(map(int, input().split()))
# 큰 수부터 내림차순 정렬하기
data.sort(reverse=True)

a, b = data[0], data[1]

result = (k * a + b) * (int(m / (k + 1))) + (m % (k + 1)) * a

print(result)