[코딩테스트/Python] Greedy 알고리즘 예제/ 큰수의 법칙

큰수의 법칙 예제

법칙

1. 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 m번 더하여 가장 큰 수를 만드는 법칙

2. 단, 배열의 특정한 인덱스에 해당하는 수가 연속하여 k번을 초과하여 더해질 수 없음

3. n=배열의 크기 ; m = 숫자가 더해지는 횟수 ; k:한번에 더할 수 있는 수  

---

WHY Greedy?

"가장 큰" 수를 만드는 알고리즘=> 전형적인 그리디 알고리즘이라고 할 수 있다!

아이디어 생각해보기 

1. 큰수데로 정렬 수 첫번째, 두번째큰 수만 뽑아두기 -> 그외의 숫자는 필요없어

2. 젤 큰거 k번 더하고 두번째 큰거 1번 더하는 수열 반복 (젤 큰수가 두개 있으면 그냥 그거 싹 더하면됨)

 

---

나의 풀이

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

arr1= sorted(arr, reverse=True)
n_max = arr1[0] ; n_second =arr1[1]

answer = 0 
while True: 
    for i in range(k):
        if m ==0: #m이 0일 경우는 더할게 없음
            break
        answer += n_max #k번만큼 더하기
        m-=1 #m횟수 감소
    if m ==0: 
        break
    answer += n_second
    m-= 1
    
print(answer)

time:8.52

피드백: 굳이 sorted 내 reverse까지 안쓰고 풀었어도 됐을 것 같기도 하고,,

 

허점) 숫자가 커질 경우 런타임 에러가 날 수도 있다!

 

교제 풀이 

큰수 k개 + 두번째 큰수 1개 의 k+1 수열로 생각하고 풀 수 있다

=> 반복문 미사용으로 시간 복잡도 크게 줄일 수 있다!

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

arr1= sorted(arr, reverse=True)
n_max = arr1[0] ; n_second =arr1[1]

cnt = int(m/(k+1))*k
cnt += m %(k+1)

answer= 0 
answer+= cnt*n_max
answer += m-cnt) *n_second
print(answer)

time:7.47

 

[reference]

도서 "이것이 코딩 테스트다" (https://github.com/ndb796/python-for-coding-test)