[Algorithm](이코테) 그리디 - 큰 수의 법칙

교재 : 이것이 코딩 테스트다 with 파이썬
Chapter 03. 그리디
실전문제 02. 큰 수의 법칙

문제

큰 수의 법칙이란 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다.
단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과해 더할 수는 없다.

입력
배열의 크기 N, 숫자가 더해지는 횟수 M, 연속해서 숫자를 최대로 더할 수 있는 횟수 K

출력
큰 수의 법칙에 따라 더해진 답

예시

• 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M=8, K=3이라고 가정하자. 특정한 인덱스의 수를 연속해서 3번까지 더할 수 있으므로 큰 수의 법칙에 따라 결과는 6+6+6+5+6+6+6+5=46이 된다.
• 다른 예시로 3, 4, 3, 4, 3으로 이루어진 배열이 있을 때 M=7, K=2라고 가정하면, 결과는 4+4+4+4+4+4+4=28이 된다. (다른 인덱스의 4이기 때문에 계속 4를 더할 수 있다)

풀이

방법 1
'가장 큰 수를 K번 더하고, 두번째로 큰 수를 1번 더하는 연산'을 반복하면 된다. (이 풀이법 까지는 내가 생각해냄!)

# 큰 수의 법칙
# 방법 1

N = 5
M = 8
K = 3
data = [2, 4, 5, 4, 6]
# 입력값 입력받기
# N, M, K = map(int, input().split())
# data = list(map(int, input().split()))

data = sorted(data, reverse=True)  # 내림차순 정렬
first = data[0]  # 가장 큰 값
second = data[1]  # 두번째로 큰 값
result = 0

while True:
    for i in range(K):
        if M == 0:
            break
        result += first
        M -= 1  # 더할때마다 1씩 빼기
    if M == 0:
        break
    result += second
    M -= 1
print(result)

while문을 보면 먼저 for문에서 가장 큰 수를 K번 더하고, 더할때마다 M의 값을 1씩 감소시킨다. 후에 if문에서 두번째로 큰 수를 1번 더한다.
숫자를 몇 개 더 더할 수 있는지 의미하는 M이 0인지 확인한 후에 result에 배열의 원소를 더한다.
👉 나는 for문만 사용하고, M값을 변화시키지 않아서 덧셈을 8번 이상 수행하고 정답을 못 찾는 코드를 짰다. while문 사용에 더 익숙해져야겠다.

방법 2
가장 큰 수, 두번째로 큰 수가 몇 번 더해지는지 구하기

# 방법 2
N = 5
M = 8
K = 3
data = [2, 4, 5, 4, 6]
# 입력값 입력받기
# N, M, K = map(int, input().split())
# data = list(map(int, input().split()))

data = sorted(data, reverse=True)  # 내림차순 정렬
first = data[0]  # 가장 큰 값
second = data[1]  # 두번째로 큰 값

count = int(M/(K+1)) * K  # M이 (K+1)로 나누어 떨어지는 경우
count += M % (K+1)  # M이 (K+1)로 나누어 떨어지지 않는 경우

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

위의 예시에서는 수열 {6, 6, 6, 5}가 2번 반복되는데, 이는 M / (K+1)번 반복되는 것이다. (8/4=2)
가장 큰 수는 M이 (K+1)로 나누어 떨어지면 수열은 (M / (K+1))xK번 반복되고, 나누어 떨어지지 않으면 M % (K+1)번 더 반복된다.
👉 가장 큰 수는 총 (M / (K+1))xK + M % (K+1)번 반복된다.
👉 두 번째로 큰 수는 (M-가장 큰 수가 반복되는 횟수) 만큼 반복된다.

References
이것이 코딩 테스트다 with 파이썬 - 나동빈 저