[그리디] 큰 수의 법칙

n 개의 다양한 수로 이뤄진 배열이 있다. 그 수들을 m 번 더해서 가장 크게 만들어야 한다. 단, 배열안의 특정 수가 k번 초과해서 더해질 수는 없다. 예를들어 n이 5인 [2,4,5,4,6] 배열로 m이 8, k가 3(8번 더하지만 특정 수가 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 = 28이 된다.

 

 

결국 배열에서 필요한 숫자는 가장 큰 수와 그다음 큰수 두개 뿐이다. 그래서 먼저 배열을 정렬하는게 첫 이슈인데 책에서 정렬까지 직접 구현하진 않았고 라이브러리를 이용했다.

# 큰수의 법칙
# 5 8 3
# 2 4 5 4 6 => 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(result)

무한 루프를 돌면서 result 값을 채울 때 마다 m 카운트를 줄여간다. m이 0이 되면 루프를 빠져나간다. 가장 큰 수를 k 번 계속 더해야 되니까 무한 루프 안에 for문이 존재하고 거기서 first(가장 큰 수)를 계속 더한다. 그리고 second(두번째로 큰 수) 를 한번 더해주고 이후부터는 반복이다.

 

책에서는 m 값이 엄청 커질때 까지 고려한 풀이도 알려준다. 수학적으로 식을 만든다. 핵심은 first(가장 큰수)를 총 몇번 더하는가이다.

총 m번을 더해야 하는 상황에서 반복 internal은 k+1개다(k번의 first 그리고 1번의 second). 그러므로 m을 k+1로 나눈 몫은 반복횟수이고 여기다가 k를 곱하면 first가 더해지는 총 횟수이다.

 

하지만 이는 m을 k+1로 나눠서 나머지없이 딱 떨어졌을 때 얘기고 나머지가 있다면 추가적으로 횟수를 더해줘야 한다(m%(k+1)). 나머지 쪽은 second 없이 first만 더해지는 횟수이므로 이렇게만 해줘도 충분하다.

# 큰수의 법칙
# 5 8 3
# 2 4 5 4 6 => 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

count = (m//(k+1))*k
count += m%(k+1)

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

print(result)

 

first 가 더해지는 총 횟수를 count 로 뒀는데, second 가 더해지는 총 횟수는 m-count 이다. 만약 문제가 더 복잡해져 third(세번째로 큰 수) 까지 더해야 하는 상황이라면 m-count 로는 못하겠지만 이 문제에서는 충분하다.

 

출처: 이것이 코딩 테스트다 나동빈 저