[Greedy] 큰수를 만들기

문제

배열(arry)에 들어가 있는 수를 M번 더하여 가장 큰수를 만드는 방식

단 배열의 특정 위치에 해당하는 수가 연속 K번 더해질 수는 없음

 

예시 )

K=3, M=5일때

5, 4, 2, 6, 7 -> 7+7+7+6+7

 

• 가장 큰수를 만드는 것이기 때문에 data들을 정렬하여 가장 큰 수를 찾는다
• 정렬의 경우에는 logN의 시간이 걸리는 최대 heap을 사용함
• 가장 큰수를 K번 더하면 더 더할 수 없으니 두번째 수를 한번 더하고 다시 가장 큰수를 더한다
• 즉, 가장 큰수와 두번째로 큰수를 번갈아(K번 + 1번) 더하면 됨

import sys
import heapq
input = sys.stdin.readline

arry = []

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

data = list(map(int, input().split()))

for i in range(0, N):
    heapq.heappush(arry, (-data[i], data[i]))

print(arry)

sum = 0
cnt = 0
flag = 1
first = heapq.heappop(arry)[1]
second = heapq.heappop(arry)[1]
while cnt<M:
    
    if flag ==1:
        
        for i in range(0, K):
            if cnt < M:
                sum += first
                cnt += 1
            else:
                break
        flag = 0

    elif flag == 0:
        sum += second
        cnt += 1
        if cnt >= M:
            break
        flag = 1

print(sum)

 

data가 100억이 된다면 10^9을 초과하므로 시간 초과가 될 수 있다.

규칙성을 이용하여 수학적으로 풀어보자

 

• K+1번의 수열로 파악할 수 있다 (제일 큰수 K번 더하기 + 두번째로 큰수 1번 더하기)
• M을 K+1로 나누고 몫과 나머지를 통해서 최대의 수를 구할 수 있다

sum = 0
cir_num = K + 1
sum += (M/cir_num) * (first*K + second)
sum += (M%cir_num) * first

print(sum)