그리디-큰 수의 법칙

이 문제를 for문과 while문을 사용해서 풀면 시간 초과가 발생할 수 있다. 

 

그렇기에 반복되는 수열에 대해 먼저 파악을 해야 한다.

# N, M, K를 공백을 기준으로 구분하여 입력 받기
n, m, k = map(int, input().split())
# N개의 수를 공백을 기준으로 구분하여 입력 받기
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) # 최종 답안 출력

N은 몇개 입력 개수, M은 숫자가 더해지는 횟수, K는 연속해서 K번까지만 더할 수 있다.

몫은 int(A/B)나 A // B로 표현한다.

 

k번까지만 연속하게 할 수 있으니 가장 큰 수가 K번 더해지고 두번째로 큰수가 더해진다. 따라서 K+1번까지가 하나의 수열이 된다. 그러면 M // (K+1)에다가 K를 곱하면 (M // (K+1)) * K가 가장 큰 수가 더해지는 횟수이고 만약 한번에 나눠떨어지지 않으면 (M // (K+1)) * K에다가 M을 K+1로 나눈 나머지만큼 더해줘야 가장 큰 수가 더해지는 횟수이다. 따라서 가장 큰 수가 몇번 사용되었는지 알려면 (M // (K+1)) * K + (M % (K+1))을 해줘야한다.