큰 수의 법칙 [그리디 알고리즘]

그리디 알고리즘 실전 문제

큰 수의 법칙

🐾 문제 설명

동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다.
단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여는 더해질 수 없는 것이 이 법칙의 특징이다.
배열의 크기 N, 숫자가 더해지는 횟수 M과 최대 연속 덧셈 가능 횟수 K가 주어지고, 배열의 N개의 숫자가 주어질 때 동빈이의 큰 수의 법칙에 따른 결과를 출력하는 문제이다.

🐾 입출력 예시

• 입력
  5 8 3
  2 4 5 4 6
• 출력
  46

🐾 내 풀이

풀이 1) sort를 이용한 풀이

N, M, K = map(int, input().split())
arr = list(map(int, input().split()))

arr.sort()

cnt = 0
tmp = 0
sum = 0
while(cnt < M):
    if tmp < K:
        sum += arr[-1]
        tmp += 1
        cnt += 1
    else:
        sum += arr[-2]
        tmp = 0
        cnt += 1

print(sum)

배열을 크기 순으로 정렬한 이후 문제의 설명을 직관적으로 구현한 코드이다.

풀이 2) sort를 이용하지 않은 풀이

N, M, K = map(int, input().split())
arr = list(map(int, input().split()))

max1 = 0
max2 = 0
for i in arr:
    if max1 < i:
        max2 = max1
        max1 = i
    elif max2 < i:
        max2 = i    

cnt = 0
tmp = 0
sum = 0
while(cnt < M):
    if tmp < K:
        sum += max1
        tmp += 1
        cnt += 1
    else:
        sum += max2
        tmp = 0
        cnt += 1

print(sum)

풀이 1과 거의 동일한 풀이이며, 풀이 1의 sort()를 통한 시간 복잡도 nlog(n)을 줄일 수 있도록 for 문을 통해 n의 시간 복잡도로 배열의 최대값과 두번째 큰 값을 구하도록 하였다.

풀이 3) 수학적 계산을 통한 풀이

N, M, K = map(int, input().split())
arr = list(map(int, input().split()))

max1 = 0
max2 = 0
for i in arr:
    if max1 < i:
        max2 = max1
        max1 = i
    elif max2 < i:
        max2 = i    

sum = (max1 * K + max2) * (M // (K + 1)) + max1 * (M % (K + 1))

print(sum)

입력의 크기가 커져 그리디 알고리즘으로의 풀이가 시간 초과 판정을 받을 경우을 대비하여, 수학적 아이디어를 통해 보다 효율적으로 문제의 풀이 방법을 작성하였다.

🐾 답안 예시

< 이것이 취업을 위한 코딩 테스트다 with 파이썬 > 답안 예시

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)

---

참고자료
이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈