[Greedy] 큰 수의 법칙

1. 규칙

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

• 입력조건

1. 첫째 줄에는 N, M, K의 자연수가 주어지며 공백으로 이를 구분한다.
2. 둘째 줄에는 N개의 자연수가 주어진다.
3. 입력으로 주어지는 K는 M보다 항상 작거나 같다.

• 입&출력
  입력
  5 8 3
  2 4 5 4 6
  출력
  46

2. 접근법

그리디 문제들을 접하면서, 느낄 수 있는 점은 큰 수를 통한 공략이 빠른 해결점이라는 것이다.

그리하여, 주어진 리스트를 통해 가장 큰 값을 출력해야하는 이번 문제 같은 경우에서는 최대한 많이 최대 값을 더하는 것이 중점이라 생각이 들었다.

이에 따라, 최대 값과 2번째로 큰 값을 별도로 저장하여, K번만큼 최대 값을 더 한후 두번쨰로 큰 값을 한번 더하여 연속된 최대 값의 사용을 끊어주는 역할을 하였다.

3. 코드

n, m, k = map(int, input().split())
data = list(map(int, input().split()))
result = 0
first = data[n-1]
second = data[n-2]

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)