[25.05.19] 그리디 알고리즘

 

[개념]

매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음

기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시해줌

즉, 정렬 알고리즘과 같이 사용되는 경우가 많음

경우에 따라 최선의 해를 구하는게 아닐 수 있음. 예를 들어 800원이 잔돈인데 지폐단위가 [500,400,100,50,10]인 경우

 

[코드]

n = 1260 #잔돈
count = 0 #잔돈 갯수

coin_types = [500, 100, 50, 10]

for coin in coin_types:
	count += n // coin
    n %= coin
    
 print(count)

화폐의 종류가 K개라고 할 때 위 소스 코드의 시간 복잡도는 O(K)

 

[예제1]

입력 조건 

배열의 크기  N, 숫자가 더해지는 횟수 M, 그리고 K

- 2 <= N <= 1000, 1 <= M <= 10000, 1 <= K <= 10000의 자연수가 주어지며, 각 자연수는 공백으로 구분

- N개의 자연수가 주어지며, 각 자연수는 공백으로 구분됨. 단, 가각 자연수는 1이상 10000이하의 수로 주어짐

- 입력으로 주어지는 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]

result = 0

while True:
	for i in range(k):
		if m == 0:
                break
        result += first
        m-= 1
     if m == 0:
     	break
     result += second
     m -= 1
     
print(result)

이렇게 재시되어 있는데

data[-1] * k * (m//(k+1)) + data[-2] * (m-k*(m//k))로 while문 안쓰는건 어떨까?

-> 두번째 답안 예시에서는

count = int(m / (k+1)) * K + M % (k +1)

result += (count) * first

result += (m-count) * second

 

map 관련 참고 자료 : https://dotiromoook.tistory.com/28

[python] map 함수 사용법, 동작원리 및 특징 (예제포함)