[그리디 / python] 큰 수의 법칙

✔️문제풀이 1 :단순하게 푸는 방법

n,m,k = map(int, input().split())
data=list(map(int, input().split()))

data.sort()

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

result=0

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

    #k번 더한 후
    if m==0: #m이 0이면 반복문 탈출
        break

    # m이 0이 아니라면 두번째로 큰 수를 한 번 더하기
    result+=second
    m-=1 #더할 때마다 1씩 뺴기

print(result)

가장 큰 수를 k번 더하고 두번째로 큰 수를 한번 더하는 연산 반복

 

✔️문제풀이 2 :반복되는 수열을 파악해서 푸는 방법

n,m,k=map(int, input().split())
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)

1. 연속으로 k번을 초과하여 더해질 수 없으므로 k+1번이 반복되는 수열의 길이이다.

2. m번 더하여 가장 큰 수를 만들라고 했으므로 m/(k+1) 이 나누기의 몫이 수열이 반복되는 횟수이다.

3. 여기에 k번을 곱해주면 m/(k+1)*k 가장 큰 수가 등장하는 횟수가 된다.

4. !!m이 (k+1)로 나누어떨어지지 않는 경우도 있으므로 m%k+1과 같이 나머지만큼 가장 큰 수가 추가로 더해질 수 있도록 해준다.