90. 큰 수의 법칙

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

• 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.

입력값 2,4,5,4,6에서 M이 8이고, K가 3이라고 가정할 때,
이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6+6+6+5+6+6+6+5인 46이 된다.

• 단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다.

• 배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때, 큰 수의 법칙에 따른 결과를 출력하시오.

• 입력조건

  • 첫째 줄에 N(2 ≤ N 1000), M(1 ≤ M ≤ 10000), K(1 ≤ K ≤ 10000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.

  • 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다.

    • 단, 각각의 자연수는 1 이상 10000이하의 수로 주어진다.

  • 입력으로 주어지는 K는 항상 M보다 작거나 같다.

• 출력조건

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

1. 단순하게 푸는 답안

#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:
      break
    result += first
    m -= 1 #더할 때마다 1씩 빼기

  if m == 0:
    break
  result += second #두번째로 큰 수 한 번 더하기
  m -= 1 #더할 때마다 1빼기

print(result)

• 단, 이 풀이는 M의 크기가 100억 이상처럼 커진다면 시간 초과 판정을 받을 것이다.

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

count = int(m/ (k + 1)) * k #가장 큰 수가 더해지는 횟수 계산
count += m % (k + 1) # 나누어 떨어지지 않는 경우

result = 0
result += (count) * first #가장 큰 수 더하기
result += (m-count) * second #두 번째로 큰 수 더하기

print(result)

• 이 문제를 풀려면 가장 먼저 반복되는 수열에 대해서 파악해야 한다.

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

  • 그렇다면 반복되는 수열의 길이는 어떻게 될까?

  • 바로 (K + 1)이 된다. 따라서 M을 (K + 1)로 나눈 몫이 수열이 반복되는 횟수가 된다.

    • 다시 K를 곱해주면 가장 큰 수가 등장하는 횟수가 된다.

  • 이때, M이 (K + 1)로 나누어 떨어지지 않는 경우도 고려해야 한다.

    그럴 때는 M을 (K + 1)로 나머지만큼 가장 큰 수가 추가로 더해지므로 이를 고려해주어야 한다.

• 즉, 가장 큰 수가 더해지는 횟수는 다음과 같다.

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