[알고리즘 / Algorithm] chapter 3. Greedy Algorithm (그리디 알고리즘) -큰 수의 법칙

출처 : 이것이 취업을 위한 코딩 테스트다  with  파이썬(나동빈 저 / 한빛미디어)  

Greedy Algorithm (그리디 알고리즘) 

 

<문제>

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

단, 배열의 특정한 인덱스에 해당하는 수가 연속으로 K번을 초과해 더해질 수 없다는 것이 특징이다.

 

입력조건 

첫째 줄에 N(2≤ N ≤1,000) , M(1≤ M ≤10,000), K(1 ≤ K ≤10,000) 의 자연수가 주어지며 각 자연수는 공백으로 구분한다.

둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 자연수는 1 이상 10,000이하의 수로 주어진다.

입력으로 주어지는 K는 항상 M보다 작거나 같다. 

 

 

출력조건

첫째 줄에 큰 수의 법칙에 따라 더해진 답을 출력한다. 

 

<아이디어>

1. 주어진 수를 M번 더했을 때 가장 큰 수가 나오려면, 배열에서 가장 큰 수를 계속해서 더하면 되지않을까? -> sort 

2.  배열에서 가장 큰 수를 K번 더하고 K+1번째에 배열에서 두번째로 큰 수를 더하자.

3. M을 K로 나눴을 때의 몫과 배열의 가장 큰 수를 곱하고, M을 K로 나눴을 때의 나머지와 배열의 두번째로 큰 수를 곱하면 문제에 따른 큰 수를 구할 수 있다. 

 

예외 추가) 

 

ex) M=7 , K=2, N = 5 (4,5,6,7,8) 일 때

 

8 + 8 + 7 + 8 + 8 + 7 + 8  이렇게 계산을 해야지 가장 큰 수가 나올 수 있는데 

이건 위의 아이디어로는 계산이 어렵다. 

 

 

 

 

<코드>

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

arr = sorted(arr) 
 
max_value = arr[N-1] * K  #max_value 는 최대 K번 곱해질 수 있다.
s_max_value = arr[N-2] * 1 
#s_max_value는 max_value가 K번 곱해지는 것을 방지해주는 역할이므로 1번만 곱해져도 상관없다. 

max_count = M // K  #max_value는 전체 M을 K번으로 나눴을 때의 몫만큼 곱해진다. 
s_max_count = M % K #s_max_value는 전체 M을 K번으로 나눴을 때의 나머지만큼 곱해진다. 

print(max_value * max_count + s_max_value * s_max_count)

 배열의 sort 메소드를 사용하지 않고 sorted() 함수를 썼다. 

▼ 밑의 링크를 참고 ▼

https://growingarchive.tistory.com/136?category=920353

[Python/Error] 파이썬 list 정렬 (sort / sorted)

 

<예시 코드>

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

data = list(map(int, input().split(" ")))

data.sort() #나는 데이터를 sort해서 다시 새로운 변수에 담으려고 했기 때문에 sort가 아닌 return 값이 있는 sorted를 사용했다.

# 큰 수의 법칙에서는 가장 큰 수와 그 다음 큰 수만 필요하다. 
first = data[N-1]
second = data[N-2]

result = 0

while True :
    for i in range(K):
        if M == 0 :
            result += first
            M -=1
        if M == 0 :
            break
        result += second
        M -=1


print(result)