오늘은 피곤한 관계로 스프링을 넘어간다.
그리디 알고리즘
- 그리디 알고리즘, 큰 수의 법칙을 구현하는 것을 배웠다. 예로, 길이가 n인 배열에서 m번의 덧셈으로 가장 큰 수를 만드는 방법은 가장 큰 요소를 m으로 곱하면 된다. 여기서 k가 그걸 제한한다. k는 한 번에 가능한 덧셈의 수를 제한한다.
- 예시로, [1,2,3,4,5]란 배열에서 7이란 m이 주어지고, 4란 k가 주어지면, 가능한 최대 덧셈은 다음과 같다.
5 + 5 + 5 + 4 + 5 + 5 + 5 - 위를 다음과 같은 코드로 구현했다.
n, m, k = map(int, input().split())
data = list(map(int, input().split()))
data.sort(reverse=True)
result = (m // (k + 1)) * k * data[0]
result += (m // (k + 1)) * data[1]
result += (m % (k + 1)) * data[0]
print(result)
이에 대해서 다음 백준 문제를 풀이했다.
오늘의 TIL 끝!