Greedy

Greedy

현재 상황에서 지금 당장 좋은 것만 고르는 방법

대부분의 문제가 그리디 알고리즘을 이용했을 때 최적의 해를 찾을 수 없을 가능성이 다분하다.

탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 잇따는 보장이 있을 때 매우 효과적이고 직관적이다.

어떤 코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해본다. 만약 오랜 시간을 고민해도 그리디 알고리즘으로 해결 방법을 찾을 수 없다면 DP나 그래프 알고리즘 등 다른 알고리즘을 고려해본다.

---

예제 3-1 거스름돈

문제

거스름돈으로 사용할 500원,100원,50원,10원짜리 동전이 무한히 존재한다고 가정함

손님에게 거슬러 줘야할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라

단, 거슬러 줘야 할 돈 N은 항상 10의 배수다.

 

나의 해답

N을 지금 줄 수 있는 거스름돈 중 가장 큰 금액 단위로 나눈다. 이때 몫이 K , 나머지가 S라면 큰 금액 단위로 K번 주고 S만큼은 다음으로 큰 금액으로 나눠 반복한다. K들을 다 더하면 최소 개수를 구할 수 있다

 

참고

동전의 단위가 서로 배수 형태가 아니라, 무작위로 주어진 경우에는 그리디 알고리즘으로 해결할 수 없고, 다이나믹 프로그래밍으로 해결할 수 있음

---

백준 문제

5585번: 거스름돈

문제

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.

입력

입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있다.

출력

제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오.

코드

# 타로에게 받아야할 돈
N = int(input())

#거스름돈
M = 1000-N
#잔돈
coins = [500,100,50,10,5,1]
# 잔돈개수
count = 0
#잔돈 종류만큼 반복
for coin in coins:
    count += M//coin # 잔돈으로 나눈 몫만큼 동전을 준다
    M = M%coin # 잔돈으로 나눈 나머지를 다음으로 작은 잔돈 크기로 나눈다.
print(count)

---

예제 3-2 큰수의 법칙

문제

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다.

배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 동빈이의 큰 수의 법칙에 따른 결과를 출력하시오

나의 해답

배열에서 가장큰 숫자와 그 다음으로 큰 숫자를 가진 인덱스를 찾는다. 가장 큰 숫자를 가진 인덱스가 i, 다음으로 큰 숫자를 가진 인덱스가 j라고 하면 i를 k번 더한 다음,j를 한번 더하고, 다시 i를 k번 더한다. 이렇게 반복해서 M번 더한다.

코드

N,M,K = map(int,input().split())
arr = list(map(int,input().split()))
arr.sort()
first = arr[N-1]
second = arr[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)

하지만 위의 코드는 M의 크기가 100억 이상처럼 커진다면 시간 초과 판정을 받을 것이다.

그래서 반복하면서 조건을 확인하는 것이 아니라, 처음부터 더해질 횟수를 알고 있다면 짧은 시간 내에 문제를 해결할 수 있다.

 

큰 수를 더할 땐 반복되는 수열이 있다.

가장 큰 수를 K번 더하고 두번째 큰 수를 1번 더한다.

즉 길이가 K+1인 수열을 반복해서 더한다.

총 숫자가 더해져야하는 횟수 M을 K+1 로 나누면 수열이 몇번 반복되는지 확인할 수 있다.

 

가장 큰 수가 더해지는 횟수는 M/(K+1)*K + M%(K+1) 이다.

두번째로 큰 수가 더해지는 횟수는 M-(가장 큰 수가 더해진 횟수) 이다.

 

코드

N,M,K = map(int,input().split())
arr = list(map(int,input().split()))
arr.sort()
first = arr[N-1]
second = arr[N-2]
result = 0

count =  int(M/(K+1)*K)
count += int(M%(K+1))
result += first * count
result+=second*(M-count)

print(result)