그리디 알고리즘 - 큰 수의 법칙

문제

출처: 2019 국가 교육기관 코딩 테스트

다양한 수로 이루어진 배열이 입력될 때 주어진 수들을 M번 더하여 가장 큰 수를 만들어야 한다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다.

• 첫째 줄에 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 = 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 + m % (k+1)
sum = first * count + second * (m - count)

print(sum)        

• m의 길이에서 한 반복당 k개의 first와 1개의 second가 반복되며 더해진다.

• 즉, m의 길이에서 (k+1)개의 세트로 반복이 된다. -> k first + 1 second

• 따라서 m // (k+1)의 몫에서 k를 곱하여 first가 최대로 나올 수 있는 횟수를 구해준다.

• 단, m이 k+1로 나누어지지 않는 경우도 존재하므로, 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
x = 1

for i in range(m): 
    if x % k != 0:
        result += first     
    else:
        result += second
    x += 1

print(result)

• m의 길이 내에서 first가 더해지는 횟수를 저장하는 x를 선언한다.

• x는 1부터 시작함에 주의한다.

• x가 k의 배수가 될 시에는 second를 result에 더하고, 그렇지 않은 경우에는 first를 계속 더해준다.