큰 수의 법칙 - 그리디 알고리즘

이것이 취업을 위한 코딩테스트다 92쪽

N, M, K = map(int, input().split())
input_array = list(map(int, input().split()))

for i in range(N-1):
    for k in range(i, -1, -1):
        if input_array[k] <= input_array[k+1]:
            input_array[k], input_array[k+1] = input_array[k+1], input_array[k]

i = 1
total_sum = 0
while i <= M:
    if i % (K+1) == 0:
        total_sum += input_array[1]
    else:
        total_sum += input_array[0]
    i += 1

print(total_sum)

문제 풀이 방법

N개의 배열 중 숫자를 골라 M번 반복하여 최대 합을 만들어내야 한다. 중복된 인덱스는 K번만 사용할 수 있다.

이 문제를 풀기 위해서는 가장 큰 값 2개를 고르고, 최대값1 x K+최대값2+최대값1 x k이런 식으로 반복하면 된다.

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

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

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

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

print(result)

간단한 코드

sort()함수를 사용하고, 더하는 횟수를 미리 구해놓으면 시간 복잡도를 줄일 수 있다.

개선 방향

• sort()함수를 적극 이용할 것
• 규칙이 있을 때는 연산을 활용할 것