CodingTest/다이나믹 프로그래밍

효율적인 화폐 구성

seongduck 2022. 7. 14. 21:21

1. 문제 설명

출처 : 이코테2021


2. 문제 조건

  • 2가지(N)으로 총합 15(M)을 만들기 위해 2원화폐와 3원화폐
  • 3가지(N)으로 총합 4(M)을 만들기 위해 3,5,7원 화폐

3. 문제 해결 아이디어

 

[Step 0]

  • N = 3, M = 7이고, 각 화폐의 단위가 2, 3, 5인 경우를 확인
  • 초기화 작업
    • 먼저 각 인덱스에 해당하는 값으로 INF(무한)의 값을 설정
    • INF는 특정 금액을 만들 수 있는 화폐 구성이 가능하지 않다라는 의미
    • 10,001을 사용가능
      • 1~7까지는 만들수 없는 무작위의 값을 설정

  • 인덱스(0) = 0원을 만들기 위한 최소한의 화폐 개수는 0

 

[Step 1]

  • 첫 번째 화폐 단위인 2를 확인한다.
  • 점화식에 따라서 다음과 같이 리스트가 갱신된다.

  • 인덱스 2원을 만들 수 있는건 1개
  • 인덱스 4원을 만들 수 있는건 2개(2원 2개)
  • 인덱스 6원을 만들 수 있는 건 3개(2원 3개)
  • 반면 1,3,5원은 만들 수 없다.

 

[Step 2]

  • 두 번째 화폐 단위인 3을 확인한다.
  • 점화식에 따라 리스트를 갱신시킨다.

  • 인덱스 3, 6원을 만들기 위해 각각(1개, 2개가 필요하다.)
  • 7원은 기본적으로 만들 수 없었지만 단위가 3인 화폐를 이용하고 있으므로 앞으로 3칸 움직여 (인덱스 4)의 값을 가져와 1을 더해준다.

 

[Step 3]

  • 세 번째 화폐 단위인 5를 확인한다.
  • 점화식에 따라 리스트를 갱신시킨다.

  • 인덱스 5원은 2개에서 1개로 바뀌었고 7원또한 화폐단위가 5이므로 5칸 앞으로가서 (인덱스 2원)의 값에 1을 더한다.

4. 답안

n, m = map(int, input().split())
#n개의 화폐 단위 정보를 입력받기
array = []
for i in range(n):
    array.append(int(input()))

#DP 테이블 초기화
d = [10001] * (m + 1)

#바텀 업방식
d[0] = 0
for i in range(n):
    for j in range(array[i], m + 1):
        if d[j - array[i]] != 10001:#(i - k)원을 만드는 방법이 존재하는 경우
            d[j] = min(d[j], d[j - array[i]] +1)
#계산된 결과 출력
if d[m] == 10001: #최종적으로 M원을 만드는 방법이 없는 경우
    print(-1)
else:
    print(d[m])
  • 화폐의 개수n, 만들고자 하는 값 m을 작성
  • 각각의 화폐의 단위를 확인하므로 for문을 중첩

 

'CodingTest > 다이나믹 프로그래밍' 카테고리의 다른 글

병사 배치하기  (0) 2022.07.14
금광  (0) 2022.07.14
1로 만들기  (0) 2022.07.14
개미 전사  (0) 2022.07.14
다이나믹 프로그래밍 개요 (피보나치 수열)  (0) 2022.07.13