[Python] 이코테_큰 수의 법칙

💡 큰 수의 법칙
이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈)
: 92p

문제

• 다양한 수로 이루어진 배열이 있을 때, 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙

• 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 특징

  [2, 4, 5, 4, 6], M=8, K=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

입력 조건

• 첫째 줄에 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 4 6

출력 예시

46

풀이

아이디어

• 그리디 알고리즘
  - 탐욕법으로 현재 상황에서 지금 당장 좋은 것만 고르는 방법
  - 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
• 내림차순 정렬로 큰 수부터 작은 수로 정렬
• 가장 큰 수를 K번 더하고, K번이 넘으면 두 번째로 큰 수를 한 번 더한 후, 다시 가장 큰 수 K번 더하기 (M번동안)

코드

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

data.sort(reverse=True)
result = 0

while True:
    for i in range(k):
        if m == 0:
            break
        result += data[0]
        m -= 1
    if m == 0:
        break
    result += data[1]
    m -= 1

print(result)

💡 M의 크기가 100억 이상이라면?
⇒ 반복되는 수열에 대해서 파악해야 함

[2, 4, 5, 4, 6], M=8, K=3
⇒ (6 + 6 + 6 + 5) + (6 + 6 + 6 + 5) = 46

• 반복되는 수열의 길이 : (K + 1)
  ⇒ M을 (K + 1)로 나눈 몫이 수열이 반복되는 횟수
  ⇒ 다시 여기에 K를 곱해주면 가장 큰 수가 등장하는 횟수
  ⇒ M이 (K + 1)로 나누어지지 않는 경우 나머지만큼 가장 큰 수가 추가로 더해짐

• 가장 큰 수가 더해지는 횟수 : M // (K + 1) * K + M % (K + 1)

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

data.sort()
first = data[n - 1]
second = data[n - 2]

count = m // (k + 1) * k
count += m % (k + 1)

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

print(result)