그리디 Greedy

알고리즘 이론 16강

좋은 블로그가 있길래 링크를 건다

큰 수의 법칙

제목은 큰 수의 법칙인데 통계에서 배운 큰 수의 법칙이랑은 달랐다.

그냥 더할 수 있는 큰 수를 더하는 문제이다.

O(n)

answer = 0

n, m, k = map(int, input().split())

nums = list(map(int, input().split()))

nums.sort()

count = 0

for _ in range(m):
    if count < k:
        answer += nums[n - 1]
        count += 1
    else:
        answer += nums[n - 2]
        count = 0

print(answer)

오름차순으로 정렬하여 가장 큰 수를 더해주는 풀이이다.
가장 큰 수를 더해준 횟수를 저장하는 변수 count를 만들어 k 보다 작은지 판단하여 만약 k번을 초과한다면 두번째로 큰 수를 더하게 하였다.

매 회마다 더할 수 있는 가장 큰 수를 더하므로 그리디 알고리즘이라고 볼 수 있을 것이다.

확실하게 정답이 나오긴 하지만 이 풀이의 경우 O(m)의 복잡도를 지니게 된다. n은 m에 비해서 작으므로 정렬 연산을 수행해도 m이 크면 전체 복잡도에 큰 영향을 미치지 않는다. 그러므로 m이 커지면 시간 초과가 날 수도 있다고 한다.

보자마자 이렇게 풀었는데 더 효율적인 풀이가 있다 그래서 좀 얼얼했다. 효율적으로 풀 생각을 못한 것이 조금 안타까웠다.

곱셈과 나눗셈을 활용한 더 효율적인 풀이

n, m, k = map(int, input().split())

nums = list(map(int, input().split()))

nums.sort()

answer = (m // (k + 1) * k * nums[n - 1]) + (m // (k + 1) * nums[n - 2]) + (m % (k + 1) * nums[n - 1])  

덧셈과 반복문을 곱셈과 나눗셈, mod 연산을 통해 효율적으로 개선한 풀이이다.

우선, 가장 큰 수를 k번 더하고 두 번째로 큰 수를 1번 더하는 것을 한 덩어리로 생각한다.

총 연산을 해줘야 하는 횟수 m에서 (k + 1)을 나눈 몫은 한 덩어리 연산을 수행하는 횟수가 될 것이다. 나머지는 0~k 범위의 수가 나올텐데 이는 마지막으로 (k + 1) 한 덩어리 연산을 수행하고 남은 연산 횟수가 된다.

연산 횟수들을 구했으면 곱셈을 이용하여 답을 구할 수 있다.

몫에 k와 가장 큰수를 곱해줄 수 있을 것이고 1은 생략되었지만 1과 두 번째 큰 수를 곱해주어 더해주면 전체 (k + 1) 한 덩어리 연산을 수행하여 나온 결과 값이 될 것이다.

나머지는 k번까지 가장 큰 수의 덧셈 연산이 가능하므로 가장 큰 수를 곱해서 더해주면 된다.

이 풀이는 답을 구하는 연산이 O(1)이 되었으므로 가장 복잡도가 큰 파이썬의 sort() 복잡도 O(nlogn)이 된다.