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

교재 : 이것이 코딩 테스트다 with 파이썬
CHAPTER 3 그리디
실전문제 3-2 큰 수의 법칙 92p

 

문제

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

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

 

 

입력 조건

• 첫째 줄에 N (2 ≤ N ≤ 1,000) , M (1 ≤ M ≤ 10,000) , K(1 ≤ K ≤ 10,000) 의 자연수가 주어지며, 각 자연수는 공백으로 구분합니다.
• 둘 째줄에 N개의 자연수가 주어집니다. 각 자연수는 공백으로 구분합니다. 단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어집니다.
• 입력으로 주어지는 K는 항상 M보다 작거나 같습니다.

 

출력 조건

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

 

 

---

✔ Solution

N, M, K = map(int, input().split())
arr = list(map(int, input().split()))

arr.sort(reverse=True)  # 내림차순 정렬

value = (arr[0] * K + arr[1]) # 가장 큰 수 K번 두번째 큰 수 1번 더해준 값 
a, b = divmod(M, K + 1)  # a는 몫 b는 나머지
print(value * a + arr[0] * b)

 

 

✔ Solution 2

# 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] # 두 번째로 큰 수

result = 0 # 결괏값 초기화

while True:
    for i in range(k): # 가장 큰 수를 K번 더하기
        if m == 0: # m이 0이라면 반복문 탈출\
            break
        result += first
        m -= 1 # 더할 때 마다 1씩 빼기
    if m == 0 : # m이 0이라면 반복문 탈출
        break
    result += second # 두 번째로 큰 수를 한 번 더하기
    m -= 1 # 더할 때마다 1씩 빼기

    print(result)

 

 

✔ Solution 3

# 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)