[python_이코테] 그리디 알고리즘, 큰 수의 법칙

[문제]

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

 

예를 들어, 2, 4, 5, 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 + 4 + 4인 28이 도출된다.

 

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

 

[입력 조건]

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

[풀이]

풀이1 : 반복문 활용

 가장 기본적인 풀이로, m의 개수가 100억 이상이 되면 시간 초과로 문제가 풀리지 않을 수 있음. 따라서 풀이2를 고려해봐야 함.

n, m, k = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
cnt = 0
result = 0

for i in range(m):
  if cnt == k:
    result += arr[-2]
    cnt = 0
  else:
    result += arr[-1]
    cnt += 1

print(result)

 

 

풀이2 : 반복적인 수열 활용

 더해지는 수열이 반복된다는 점을 사용해 문제를 풀이

n, m, k = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
max_1 = arr[-1]
max_2 = arr[-2]
set_val = max_1 * k + max_2
result = (set_val * (m // (k + 1))) + (max_1 * (m % (k + 1)))
print(result)

 

해설 >>