[Problem Solving] 큰 수의 법칙

그리디, 탐욕법

문제 : 큰 수의 법칙

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

 

#  N : 배열의 크기, M : 숫자가 더해지는 횟수, K : 최대 연속 횟수
# 5 8 3
# 2 4 5 4 6
# 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5 = 46

n, m, k = map(int, input().split())
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):
        if M == 0:
            break
        result += first
        M -= 1
    if M == 0:
        break
    # 최대 반복 횟수가 끝나고, 그 다음으로 큰 수를 한 번 더한다.
    result += second
    M -= 1

print(f"결과 : {result}")

 

위의 방법처럼 단순하게 계산을 할 수도 있지만 간단한 수학적 아이디어를 이용해 더 효율적으로 문제를 해결할 수도 있다.

 

# 5 9 3
# 2 4 5 4 6
# 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5 + 6 = 46

# 반복되는 수열 : 6 + 6 + 6 + 5
# 반복되는 수열의 길이 : K + 1
# 반복되는 수열의 횟수 : int(M / (K + 1))
# 제일 큰 수의 반복 횟수 : int(M / (K + 1)) * K
# 나누어 떨어지지 않는 경우 : int(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]

result = 0
count = 0   # 제일 큰 수의 반복 횟수

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

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

print(f"합 : {result}")