그리디
현재 상황에서 지금 당장 좋은 것만 고르는 방법

✅ 문제

• 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.
• 배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 동빈이의 큰 수의 법칙에 따른 결과를 출력하시오.

입력 조건

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

출력 조건

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

입력 예시

5 8 3
2 4 5 6 4

출력 예시

46

💻 코드

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

a = map(int, input().split())

lst = list(a)

lst.sort(reverse=True)

result = 0

i=0

while True:
    for j in range(0, K):
        if(i == M):
            break
        result += lst[0]
        i = i+1
    if(i == M):
        break
    result += lst[1]
    i = i + 1
    
print(result)

설계

둘째 줄에 입력된 자연수들을 리스트로 변환한 후 내림차순 .sort(reverse=true) 으로 정렬하였다. i를 0으로 초기화하고 무한 루프를 돌려 연산이 이루어질 때마다 i를 1씩 증가시키고 i가 M과 같은 값이 되면 무한루프를 빠져나온다. 정렬된 리스트의 첫번째값을 K번만큼 더하고 두번째값을 한 번 더하는 연산을 반복하는 것이 가장 큰 수를 만들 수 있다.

➕ 책에 나온 다른 방법

수열 사용

수열
순서가 있는 나열

• 가장 큰 수와 두 번째로 큰 수가 더해질 때는 특정한 수열 형태로 일정하게 반복해서 더해지는 특징이 있다.

핵심!
가장 큰 수가 더해지는 횟수를 구하고 M에서 그 횟수를 뺀만큼 두번째로 큰 수를 더한다.

답안

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

data = list(map(int, input().split()))

data.sort()

first = data[-1]
second = data[-2]

count = int(M / (K + 1)) * K
count += M % (K + 1)

result = 0
result = first * count
result += second * (M - count)

print(result)

📝 정리

• 반복문을 사용하지 않고도 답을 구할 수 있는 문제였다.
• .sort(reverse=true)를 사용하지 않고 오름차순인 .sort() 후 data[-1] 과 같은 방식으로 가장 큰 수를 바로 찾을 수 있다.