[Greedy] 이코테 - 큰 수의 법칙(py)

문제

나동빈, 「이것이 취업을 위한 코딩테스트다 with 파이썬」, 한빛미디어, p.92 참고

 

풀이

- 단순 풀이 예시

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(result)

 

- 반복되는 수열 활용 풀이

=> 수열의 길이 = (k + 1), 수열이 반복되는 횟수 = m / (k + 1), 가장 큰 수가 등장하는 횟수 = 수열 반복되는 횟수 * k

+ m이 (k + 1)로 나누어 떨어지지 않는 경우 고려 (나머지만큼 가장 큰 수가 추가로 더해짐)

 

즉, 가장 큰 수가 더해지는 횟수 = int(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 = int(m / (k + 1) * k)
count += m % (k + 1)

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

print(result)