[그리디] 그리디 알고리즘 (2) 실전 문제 - 큰 수의 법칙

이코테 p.92 실전문제 - 큰 수의 법칙

내 소스코드 (for문 이용)

import sys

N, M, K = map(int, sys.stdin.readline().rstrip().split())
data = list(map(int, sys.stdin.readline().rstrip().split()))

# 내림차순 정렬
data.sort(reverse = True)
result = 0
cnt = 0

for m in range(M):
  if cnt < K:
    result += data[0]
  else:
    result += data[1]
    cnt = 0
  cnt += 1
    
print(result)

그리디 알고리즘을 이용하여 가장 큰 수를 K번 더하고, 두 번째로 큰 수를 1번 더하는 과정을 반복하면 배열로 주어진 수들을 M번 더하여 가장 큰 수를 만들 수 있음.

교재 소스코드 ver1 - 단순하게 푸는 답안 (while문 이용)

import sys

N, M, K = map(int, sys.stdin.readline().rstrip().split())
data = list(map(int, sys.stdin.readline().rstrip().split()))

# 내림차순 정렬
data.sort(reverse = True)
first = data[0]
second = data[1]
result = 0

while True:
  for k in range(K):
    if M == 0:
      break
    result += first
    M -= 1
  if M == 0:
    break
  result += second
  M -= 1
    
print(result)

 

교재 소스코드 ver2 - 시간 효율적인 답안

하지만 위와 같은 방법들은 M의 크기가 100억 이상처럼 커진다면 시간 초과 판정을 받을 것.

수학적 아이디어를 이용하여 더 효율적으로 해결 가능.

• M이 8, K가 3, 가장 큰 수가 6, 두 번째로 큰 수가 5인 경우
  • (6 + 6 + 6 + 5) + (6 + 6 + 6 + 5) = 46이 가장 큰 수가 됨
  • {6, 6, 6, 5}가 반복되어 더해짐
  • 반복되는 수열의 길이 = K + 1
  • 수열이 반복되는 횟수 =  M / (K + 1)
  • 가장 큰 수가 등장하는 횟수 = M / (K + 1) * K
  • M이 (K + 1)로 나누어 떨어지지 아ㅏㄶ는 경우, M % (K + 1)만큼 큰 수가 추가로 더해짐
  • 따라서 가장 큰 수가 더해지는 횟수 = int(M  / (K + 1)) * K + M % (K + 1)
  • 두 번째로 큰 수가 더해지는 횟수 = M - 가장 큰 수가 더해지는 횟수
• 따라서 소스코드는 다음과 같음.

import sys

N, M, K = map(int, sys.stdin.readline().rstrip().split())
data = list(map(int, sys.stdin.readline().rstrip().split()))

data.sort() # 오름차순 정렬
first = data[N - 1] # 첫 번째로 큰 수
second = data[N - 2] # 두 번째로 큰 수
result = 0

# 가장 큰 수가 더해지는 횟수
cnt = int(M / (K + 1)) * K
cnt += M % (K + 1)

result += cnt * first # 가장 큰 수 더하기
result += (M - cnt) * second # 두 번째로 큰 수 더하기
    
print(result)