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

728x90

# 큰 수의 법칙
# 주어진 수들을 M번 더해서 가장 큰 수를 만든다.
# 해당하는 수가 연속해서K번을 초과해 더해질 수는 없다.

# N, M , K 순서대로 공백 구분해서 입력받기
n, m, k = map(int, input().split())

# N개의 수 공백으로 구분해 입력받기
data = list(map(int, input().split()))

data.sort(reverse=True) # 정렬
first = data[0] # 가장 큰 수
second = data[1] # 두 번째 큰 수

result = 0

while True:
    for i in range(k): # 가장 큰 수 k번 더하기
        if m == 0: # m이 0이라면 종료
            break 
        result += first
        m -= 1 # 더할 때마다 1씩 
    if m == 0:
        break
    result += second # 두 번째로 큰 수 더하기
    m -= 1
    
print(result)

알고리즘 참고

# -*- coding: utf-8 -*-
"""
Created on Wed Mar 10 09:08:27 2021

@author: as_th
"""

# 큰 수의 법칙
# 주어진 수들을 M번 더해서 가장 큰 수를 만든다.
# 해당하는 수가 연속해서K번을 초과해 더해질 수는 없다.

# N, M , K 순서대로 공백 구분해서 입력받기
n, m, k = map(int, input().split())

# N개의 수 공백으로 구분해 입력받기
data = list(map(int, input().split()))

data.sort(reverse=True) # 정렬
first = data[0] # 가장 큰 수
second = data[1] # 두 번째 큰 수

result = 0

# =============================================================================
# while True:
#     for i in range(k): # 가장 큰 수 k번 더하기
#         if m == 0: # m이 0이라면 종료
#             break 
#         result += first
#         m -= 1 # 더할 때마다 1씩 
#     if m == 0:
#         break
#     result += second # 두 번째로 큰 수 더하기
#     m -= 1
#     
# =============================================================================

count = int(m/(k+1))*k # 가장 큰 수 더함
count += m %(k+1) # 나누어 떨어지지 않는 경우 

result += (count) * first # 가장 큰 수 더하기
result += (m-count) * second  # 두 번째로 큰 수 더하기

print(result)