[이코테] 그리디_큰 수의 법칙

1. 처음 생각한 코드

#그리디_큰 수의 법칙
n,m,k = map(int, input().split())
num = list(map(int, input().split()))

num.sort() #리스트에 있는 수들 오름차순으로 정렬

sum =0
i =0

first = num[n-1]  #가장 큰 수 저장
second = num[n-2] #두번째로 큰 수 저장

while i<m:      #인덱스가 주어진 m보다 작을 경우 연산 시작
  sum+=first*k   #sum = first를 k번 더함
  i+=k           #인덱스는 k만큼 증가(k번 더했으니까)
  if i<m:        #인덱스 다시 비교(k<=m이므로)
    sum+=second  #인덱스가 m보다 작으면 sum에 그 다음 큰 수 한번 더함
    i+=1         #인덱스 하나 증가(두번째 큰 수 한번 더했으므로)
  else:          #인덱스가 m이상일 경우
    i = i-m      #위에서 구한 인덱스에 m을 뺌        
    sum = sum- (first*i) #sum에서 넘친 만큼 뺌
    break       #while반복문 나감

print(sum)

#한줄평: m-=1를 생각못해서 조금 더 복잡하게 푼거 같다..

2. 모범 답안 참고

#그리디 큰수법칙 모범 답안
n,m,k = map(int, input().split())
num = list(map(int, input().split()))
sum = 0

num.sort()

first = num[n-1]  #가장 큰 수 저장
second = num[n-2] #두번째로 큰 수 저장

while True:
  for i in range(k): #2  1  0  2 1 0
    if m==0:         #8  7  6  4 3 2
      break
    sum+= first      #6  12 18 29 35 41
    m-=1             #m=7 6  5 3  2  1

  if m==0:           #5 1
    break            #4  0
  sum+=second      #23 46
  m-=1 

print(sum)

 

3. 그리디 수학적 풀이

#그리디 큰수법칙 수학적 풀이
n,m,k = map(int, input().split())
num = list(map(int, input().split()))
sum = 0

num.sort()

first = num[n-1]  #가장 큰 수 저장
second = num[n-2] #두번째로 큰 수 저장

sum = (m//(k+1)) * (first*k+second) + ((m%(k+1))*first) #반복되는 부분은 m//k+1 만큼 곱해주고, 남는 부분은 따로 처리

print(sum)