그리디 알고리즘
공부는
'이것이 취업을 위한 코딩테스트다 with 파이썬'
으로 진행했다.
이 문제에서는 '1이 될 때까지' 문제와 마찬가지로 쓸데없는 연산을 한 번에 계산하도록 하는 방식을 알 수 있었다.
동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때, 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.
예를 들어, 순서대로 2, 4, 5, 4, 6 으로 된 배열이 있을 때, M이 8이고, K가 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이 된다.
- 입력
-
첫째 줄에 N(2 <= N <= 1,000), M(1 <= M <= 10,000), K(1 <= K <= 10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
-
둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단 각각의 자연수는 10,000이하의 수로 주어진다.
-
입력으로 주어지는 K는항상 M보다 작거나 같다(K <= M)
- 출력
첫째 줄에 큰 수의 법칙 결과 값을 출력한다.
단순히 가장 큰 수와 두 번째로 큰 수를 뽑아서 가장 큰 수를 k번 더하고 두 번째로 큰 수를 1번 더하는 것을 반복하면 해결할 수 있는 문제이다. 하지만 특정 규칙을 찾아 이를 일반화 시키면 훨씬 효율적으로 해결할 수 있다.
위의 예시를 보면 6+6+6+5, 6+6+6+5가 반복해서 더해지고 있다. 즉 6+6+6+5를 하나의 덩어리로 보면 k+1만큼의 길이를 가진 수열이 되고, m // (k+1)은 더하는 횟수가 된다. m을 k+1로 나눈 나머지만큼 가장 큰 수를 더해주면 문제가 해결된다.
#p94
n, m, k = map(int, input().split())
data = list(map(int, input().split()))
data.sort()
first = data[n-1]
second = data[n-2]
#가장 큰 수가 더해지는 횟수를 계산한다.
count = (m // k+1) * k
count += m % (k+1)
#가장 큰 수와 두 번째로 큰 수를 더한다.
result = 0
result += count * first
result += (m - count) * second
print(result)다른건 다 필요없고
count = (m // k+1) * k
count += m % (k+1)이 부분이 핵심이다.
이렇게 사고하는 방식을 계속해서 훈련해야겠다고 느꼈다.
