큰 수의 법칙

- 문제

다양한 수로 이루어진 배열이 있을 때, 주어진 수들을 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 (6+6+6+5+6+6+6+5)

- 문제 풀이

해당 문제는 그리디 알고리즘을 적용하여 쉽게 해결할 수 있다. 주어진 배열에서 가장 큰 수와 두 번째로 큰 수를 찾고, 가장 큰 수를 K번 더한 후 두 번째로 큰 수를 한번 더하는 연산을 반복하면 된다.

프로세스를 순차적으로 나열해보면,
1. 둘째 줄에 주어진 배열을 정렬
2. 가장 큰 수와 두 번째로 큰 수를 선택
3. 반복문을 이용하여, 가장 큰 수를 K번 더한 뒤, 두 번째로 큰 수를 한번 더함
4. 수를 더할 때마다 M을 1씩 감소시키고, M이 0이 되면 반복문을 종료
5. 더한 값을 출력

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

data.sort()
first = data[-1]
second = data[-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이 10,000 이하이므로 위의 방법을 통해서 문제를 해결할 수 있지만, M의 크기가 100억 이상처럼 커진다면 시간 초과 판정을 받는다. 점화식을 이용한다면, 더 효율적으로 문제를 해결할 수 있다.

이 문제는 가장 큰 수를 K번 더한 뒤, 두 번째로 큰 수를 한번 더하는 과정을 반복한다. 이는 특정한 수열의 형태로 반복된다는 것을 뜻한다. 따라서, 반복되는 수열의 길이는 (K + 1)임을 쉽게 알아낼 수 있다.
숫자를 M번 더하는 동안, (K + 1)의 길이를 갖는 수열이 반복되는 것이기 때문에, M을 (K + 1)로 나눈다면 수열이 반복되는 횟수를 구할 수 있다.
여기서 M을 (K + 1)로 나눴을 때 나누어 떨어질 수도 있고, 그렇지 않을 수도 있다. M을 (K + 1)로 나눴을 때, 나머지는 무조건 K보다 작거나 같아야 한다. 결국 수열이 M / (K + 1)번 반복된 후, 가장 큰 수를 나머지와 같은 횟수로 더해줬다는 의미이다.
따라서 위의 내용들을 종합하여 가장 큰 수가 더해지는 횟수를 구해보면 다음과 같고,

count = int(M / (K + 1)) * K + M % (K + 1)

두 번째로 큰 수가 더해지는 횟수는 다음과 같이 표현할 수 있다.

M - count

위의 점화식을 이용하여 코드를 작성해보면

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

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

count = int(m / (k + 1)) * k
count += m % (k + 1)

result = 0
result += count * first
result += (m - count) * second

print(result)

출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, 나동빈 지음