알고리즘 / 자료구조’ 시리즈

[이.취.코] Chap 8. 다이나믹 프로그래밍 - 효율적인 화페 구성

  • 0
  • 0
0
0

1. 효율적인 화페 구성

  • 난이도
  • 풀이 시간
    • 30분
  • 시간 제한
    • 1초
  • 메모리 제한
    • 128MB

A. 문제

N가지 종류의 화폐가 있다. 화폐들의 개수를 최소한으로 이용해서 가치의 합이 M원이 되도록 만들어라. 각 화폐는 몇 개라도 사용할 수 있다.

a. 예를 들면.

2원, 3원 단위의 화폐가 있을 때 15원을 만들기 위해서는 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수다.

b. 입력 조건
  • 첫째 줄에 N, M이 주어진다
    • 1 <= N <= 100
    • 1 <= M <= 10,000
  • 이후 N개 줄에 각 화폐의 가치가 주어진다.
    • 화폐의 가치는 10,000보다 작거나 같은 자연수
c. 출력 조건
  • 첫째 줄에 경우의 수 X를 출력한다.
    • 불가능할 때는 -1을 출력한다.
d. 테스트 케이스
  • 입력 예시

    
    2 15
    2
    3
    
    
    
    3 4
    3
    5
    7
    
    
  • 출력 예시

    
    5
    
    
    
    -1
    
    

B. 내 답안


n, m = list(map(int, input().split()))  
n_array = []  
  
array = [0] * 10001  
  
result = 0  
  
for i in range(n):  
    n_array.append(int(input()))  
  
  
for i in range(0, min(n_array)):  
    array[i] = 0  
  
# array[min(n_array)] = 1  
  
for i in range(min(n_array), m+1):  
    # print(array)  
    for j in range(len(n_array)):  
        if j+1 >= len(n_array):  
            continue  
        if i-n_array[j+1] < 0:  
            continue  
        array[i] = min(array[i-n_array[j]], array[i-n_array[j+1]]) + 1  
print(array)  
if array[min(n_array)] == 1:  
    result = array[m]  
else:  
    result = -1  
  
print(result)  
  
# 47분 / 실패

a. 회고

풀이

반성

DP 맨 처음 문제에서 그래프 방식으로 문제를 해석해서 그래프 방식에 많이 의존했다.

결론

앞으로는 리스트를 표현할 때 사용하는 직사각형 모양으로 풀어야겠다.
이 방식도 나중가면 문제가 생길지 모르겠지만, 일단은 이런 방식으로 접근해보자.

C. 문제 해설

적은 금액부터 큰 금액까지 확인하며 차례대로 만들 수 있는 최소한의 화폐 개수를 찾으면 된다. 금액 i를 만들 수 있는 최소한의 화폐 개수는 a_i, 화폐의 단위를 k라고 했을 때 아래 점화식을 만들 수 있다. a_{i-k}는 금액 (i-k)를 만들 수 있는 최소한의 화폐 개수를 의미한다.

  • a_{i-k}를 만드는 방법이 존재하는 경우
    • a_{i} = min(a_{i}, a_{i-k} + 1)
  • a_{i-k}를 만드는 방법이 존재하지 않는 경우
    • a_{i} = 10001

이 점화식을 모든 화폐 단위에 대하여 차례대로 적용하면 된다. ㅅ길제로 문제를 풀기 위해서는 가장 먼저 m의 크기만큼 리스트를 할당한다. 그리고 각 인덱스를 금액으로 고려하여 메모이제이션을 진행한다.

N=3, M=7, 화폐 단위가 [2,3,5]인 경우

  1. 각 인덱스에 해당하는 값으로 10,001을 설정한다. M의 최대 크기가 10,000이므로 불가능한 수로 10,001이라는 값을 설정했으며 이보다 더 큰 수여도 상관없다. 0원일 경우 화폐를 하나도 사용하지 않았을 떄 만들 수 있으므로 값으로 0을 설정한다.

  2. 첫 번째 화폐 단위인 2부터 확인한다.

  3. 화폐 단위 3를 확인한다.

  4. 화폐 단위 5를 확인한다.

a. 책 답안

python-for-coding-test/8.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

#코딩테스트 #파이썬 #나동빈 #한빛미디어 #문제 #풀이 #다이나믹프로그래밍 #효율적인화폐구성

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.