[이것이 코딩 테스트다 with Python] 그리디 알고리즘 문제풀이 - 큰 수의 법칙

내 풀이

"""
### 동빈나 <이것이 코딩테스트다> 실전 문제
## 그리디 알고리즘 - 1. 큰 수의 법칙

# 난이도 '하' / 시간제한 1초 / 메모리 제한 128MB / 기출: 2019 국가 교육기관 코딩 테스트
# 풀이 시간제한: 30분
"""

"""
N: 배열의 크기
M: 숫자가 더해지는 횟수
K: 연속으로 더해지는 횟수 제한

Result: 주어진 수들을 M번 더해 가장 큰 수를 구하기
"""

N, M, K = map(int, input().split())
nums = list(map(int, input().split()))
result = 0

nums.sort(reverse=True)

maxNum = nums[0]
secondNum = nums[1]

while True:
    if M == 0:
        break

    for _ in range(K):
        if M == 0:
            break
        result += maxNum
        M -= 1

    result += secondNum
    M -= 1

print(result)

풀이 설명

- 가장 큰 수를 K 만큼 계속 반복해주면서 중간중간 연속이 끊기도록 두 번째 큰 수를 넣어주는 것이 포인트

- { maxNum * K + secondNum } 이 반복해서 더해지는 것

- 위 풀이에서는 반복문으로 이를 풀었지만, 가장 큰 수가 반복되는 횟수를 계산하여 그 횟수만큼 곱해서 더하는 방식으로 푸는 것이 빠르고 깔끔함 (아래 코드 참고)

다른 풀이 방법

N, M, K = map(int, input().split())
nums = list(map(int, input().split()))
result = 0

nums.sort(reverse=True)

maxNum = nums[0]
secondNum = nums[1]

# 가장 큰 수를 더하는 횟수
cnt = (M // (K+1)) * K
# 나누어 떨어지지 않을 때 더할 횟수도 추가
cnt += M % (K+1)

result += (cnt * maxNum)
result += ((M-cnt) * secondNum)

print(result)