최소비용으로 목표한 금액을 생산하는 방법은?

1. 문제

 

화폐가 1원, 5원, 10원, 50원, 100원, 500원으로 6종류가 있다.

목표하는 생산 금액 money가 주어지고

주어진 화폐 6종류의 생산 단가가 배열로 costs로 주어진다.

money만큼 화폐를 생산하는데 최소비용을 return하는 알고리즘을 작성한다면?

 

 

2. 내가 생각한 풀이

 

목표로 하는 금액 money를 target이라는 새로운 변수에 복사하고

 

money_list를 500부터 1원까지 거꾸로해서 리스트로 만든다

 

money_dict로 금액을 key로 해당 금액의 생산단가를 value로 하는 사전을 만든다

 

prod_list는 각 화폐를 몇개 생산해야하는지 나타낸 변수

 

def solution(money, costs):

    from collections import deque

    answer = 0

    target = money

    money_list = [500,100,50,10,5,1]

    money_dict = {}

    for key,value in zip(money_list,costs[-1::-1]):

        money_dict[key] = value

    prod_list = deque()

 

목표 금액을 화폐로 나누면 몫만큼 생산하고 나머지를 다른 화폐로 나눠서 또 몫만큼 생산하고... 이를 반복하면

 

각각 화폐를 몇개만큼 생산해야하는지 알 수 있다

 

    for mon in money_list:

        num,target = divmod(target,mon)

        prod_list.appendleft(num)

 

그러면 현재 prod_list에는 500원부터 1원까지 초기 생산해야하는 개수가 리스트로 들어가 있다

 

예를 들어 money=4578이라고 하자

 

money를 500으로 나누면 몫은 9이고 나머지는 78이다.

 

500원은 9개 생산하고 나머지 78원을 100,50,10,5,1로 생산한다

 

78을 100으로 나누면 몫은 0이고 나머지는 78이므로 100원은 0개

 

78을 50으로 나누면 몫은 1이고 나머지는 28이므로 50원은 1개

 

28을 10으로 나누면 몫은 2이고 나머지는 8이므로 10원은 2개

 

8을 5로 나누면 몫은 1이고 나머지는 3이므로 5원은 1개

 

3을 1로 나누면 몫은 3이고 나머지는 0이므로 1원은 3개

 

그래서 초기에 prod_list=[9,0,1,2,1,3]이 들어간다

 

------------------------------------------------------------------------------------------------------------------

 

그러면 이제 어떻게 최소단가를 맞추냐??

 

500,100,50,10,5,1 6개 각각에 대해서 하나의 금액을 기준으로 잡고

 

나머지를 그 금액만큼 생산할때 생산단가를 비교한다

 

예를 들어서 costs=[1,4,99,35,50,1000]이면 500원은 생산단가가 1000원이고 100원은 생산단가가 50원이다.

 

100원을 5개 생산하면 500원인데 이때 생산가격은 250원이다.

 

그러므로 500원 1개를 생산할바에는 100원 5개를 생산하는게 무조건 이득이다.

 

나아가서 500원 9개를 생산할바에는 100원 45개를 생산하는게 무조건 이득이다. 

 

--------------------------------------------------------------------------------------------------------------------------

 

 

따라서 500원부터 시작해서 나머지 100,50,10,5,1을 500원만큼 생산할때 생산가격을 구한다음에

 

최소 생산단가를 가지는 화폐를 찾아서 500원의 개수를 그 화폐로 모두 옮겨버린다

 

    for ind in range(-1,-6,-1):

        a = costs[ind]

        target = money_list[(-1*ind)-1]

        relative = []

        target_list = money_list[(-1*ind):]

        for mon in target_list:

            num = target//mon

            relative.append(num*money_dict[mon])

        if a > min(relative):

            min_ind = relative.index(min(relative))

            target_money = target_list[min_ind]

            target_num = target//target_money

            prod_list[ind-1] += target_num*prod_list[ind]

            prod_list[ind] = 0

 

costs=[1,4,99,35,50,1000]라고 하자.

 

500원부터 시작할거라 range(-1,-6,-1)로 잡았다.

 

a=costs[ind]를 하면 500원의 생산단가 1000원이 먼저 잡힌다

 

target에는 money_list에서 0번 원소인 500원이 잡힌다

 

target_list에는 비교 대상인 [100,50,10,5,1]이 잡힐것

 

relative에는 상대적 비용을 계산해서 집어넣을것

 

target_list에서 하나씩 빼서 mon으로 두고

 

target을 mon으로 나누면 [5,10,50,100,500]이 될것인데 이는 500원이 되기 위한 개수 num이 된다.

 

money_dict에는 화폐 금액을 key로 금액에 해당하는 생산단가가 value로 들어가서

 

num*money_dict[mon]을 하면 target만큼 mon을 생산할때 들어가는 생산가격이다

 

a는 기준값인 target=500원의 생산단가이고 min(relative)는 나머지 비교대상의 target만큼 생산할때 드는 비용이다

 

만약 min(relative)가 더 작다면 target=500만큼 생산하는 개수를 그 화폐로 모두 옮겨버리는게 이득이므로

 

그 화폐가 무엇인지 찾아야한다

 

relative.index(min(relative))를 하면 최솟값 인덱스를 찾고

 

그 인덱스를 비교대상 리스트인 target_list에 집어넣으면 상대비용 최솟값이 무슨 화폐인지 알 수 있다

 

target=500을 그 화폐인 target_money로 나누면 배수 차이를 구할 수 있다

 

예를 들어 target_money=100이면 target_num=5가 된다

 

그러면 최초 target만큼 생산한 개수 prod_list[ind]를 찾고 target_num을 곱하면 target만큼 생산한 개수를 모두 target_money 개수로 옮겨버릴 수 있다

 

마지막으로 모두 옮겼으니까 target만큼 생산하는 비용 prod_list[ind]=0으로 둔다

 

이를 모든 ind에 반복하면 최소 비용 리스트 prod_list로 바뀐다

 

    for a,b in zip(prod_list,costs):

        answer += a*b

    return answer

 

그러면 최소비용 리스트 prod_list와 생산단가 costs를 이용해서 최소 생산비용 answer를 zip for문으로 구할 수 있다

 

 

3. 돌아보기

 

이거 하나로 2시간 걸려서 코딩테스트 탈락했지만

 

핵심알고리즘 파악을 잘 했다

 

최초 생산개수를 나누기로 구하고

 

기준 금액에 대해 나머지 금액의 생산단가를 비교해서

 

생산단가가 싼 금액으로 기준 금액의 생산개수를 모두 옮기면 된다

 

폼이 많이 떨어진것 같다

 

꾸준히 연습해야겠다