[이것이 코딩 테스트다 with Python] 그리디 - 동빈이의 큰 수의 법칙

문제 > 

 

큰 수의 법칙이란 다양한 수로 이뤄진 배열이 있을 때 주어진 수들을 M번 더해 가장 큰 수를 만드는 법칙

단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과할 수는 없음

 

입력 조건 >

첫째 줄에 N(2<=N<=1000), M(1<=M<=10000), K(1<=K<=10000)의 자연수가 주어지며 각 자연수는 공백으로 구분

둘째줄에 N개의 자연수가 주어짐. 각 자연수는 공백으로 구분. 단, 각각의 자연수는 1이상 10000이하의 수로 주어짐

입력으로 주어지는 K는 항상 M보다 작거나 같다.

 

출력 조건 >

첫째 줄에 큰 수의 법칙에 따라 더해진 답을 출력

 

입력 예시

5 8 3

2 4 5 4 6 

 

출력 예시

46 

 

✏️ 풀이방법 ✨그리디유형

 

우선 들어온 숫자들을 오름차순으로 정렬을 하면 숫자가 큰순으로 정리되므로 이를 이용한다. (.sort함수)

이후 계산에는 앞의 두숫자만 이용이 되며 가장큰수가 M번 그후 그다음 큰수1번 이 반복되는 형식일 것이다.

따라서 이 M+1 이 한 덩어리 bundle 그리고 이것이 반복되는 횟수를 repeat

그리고 bundle 즉 K+1로 M이 나눠떨어지지 않는경우 남는 횟수 remainder 만큼 입력받은 숫자중 가장 큰 수를 곱해주면 되므로

# m번 더해 가장큰수. k번 초과하여 더할 수 없음
N, M, K = map(int, input().split())    
nlist = list(map(int, input().split()))
sum = 0
# 숫자 리스트를 만든뒤 이를 크기별로 정렬하고 하나씩 쓰도록할것이다.
nlist.sort(reverse=True)


repeat = M//(K+1)
bundle = (nlist[0] * K) + nlist[1]
remainder = M%(K+1)

if remainder == 0:
    tail = 0
else:
    tail = nlist[0]*remainder

sum = (bundle * repeat) + tail
print(sum)