[CodingTest] 효율적인 화폐구성 ( dp )

 

◎문제

• N가지 종류의 화폐가 있다.
• 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다.
• 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다.
• 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다.

 

- 입력 조건

• 첫째 줄에 N,M이 주어진다(1<= N <= 100, 1<= M <= 10,000)
• 이후의 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐의 가치는 10,000보다 작거나 같은 자연수이다.

 

- 출력 조건

• 첫째 줄에 경우의 수 X를 출력한다.
• 불가능할 때는 -1을 출력한다.

 

 

◎문제풀이

 

2원, 3원 .. 작은 돈으로 큰 돈을 구하는 문제이다.  부분에서 전체를 구한다는 점에서 DP를 발상할 수 있다. 문제는 화폐의 개수를 최소로 하는 것을 목적으로 한다. 그래서 그리디(Greedy)도 연상이 된다. 

 

그리디적 발상으로 문제를 접근하면 화폐 구성 중 가장 큰 금액을 최대한 많이 사용해야 최소의 개수로 목표금액에 도달 할 수 있다. 그러나 그리디 접근에는 어려운 점이 있다. 화폐구성이 동적으로 변하고 목표 금액을 정확히 맞추어야 한다. 6000원을 만드는데 2원, 3원, 5원으로 만들어야 할 수도 있고 3원, 7원, 5000원으로 만들어야 할 수도 있다. 

 

6000원을 만드는데 5000원은 1개가 최대 개수이지만 3원과 7원으로 나머지 1000원을 만들 수 없다. 그러므로 이는 그리디보다는 DP로 접근해야 한다. DP는 큰 부분을 작은 부분으로 쪼개어 문제를 해결하는 분할정복 방식이다. 이때 작은부분은 자료구조에 저장되어 반복 연산을 방지한다.

 

 

 

 

 

 

2원, 3원, 5원으로 27원을 만들려고 한다. 큰 문제를 작은 문제로 나누어 보자. 

 

27원이 되는 경우는 3가지이다. 

 

1) 25원 + 2원

2) 24원 + 3원

3) 22원 + 5원

 

3가지 경우 중에 화폐개수의 최솟값을 구해야 한다. 화폐의 개수를 D라 표현하겠다. D(2),D(3),D(5)은 모두 1개이다. 그러므로 D(25), D(24), D(22) 중 최소의 + 1이 D(27)이 된다.

 

❖ D(27) = MIN( D(25), D(24), D(22) ) + 1  // +1은  D(2),D(3),D(5)을 의미

 

D(24)가 최소라고 가정해보자. 

 

D(24)도 마찬가지로 3가지 경우가 있다.

 

1) 23원 + 2원

2) 22원 + 3원

3) 20원 + 5원

 

❖ D(24) = MIN( D(23), D(22), D(20) ) + 1 

 

이렇게 점화식이 나왔다. 구현이 쉬운 Bottom-Up 방식으로 문제에 접근해보겠다.  D(N) 데이터를 담을 테이블을 하나 생성하고 Bottom-Up으로 하나씩 테이블을 채워나가면 원하는 목표의 최소 화폐개수를 파악할 수 있다.

 

◎ 코드

MAX = 10000

n,m = map(int,input().split()) # n : 화폐개수, m : 목표금액
pocket = [] # 화폐구성 리스트
d = [MAX+1]*(m+1) # 최소개수 저장 테이블

# 화폐구성 입력받기
for _ in range(n) :
  pocket.append(int(input()))

# 화폐구성단위는 최소개수가 1개이므로 1 저장
for i in pocket :
  d[i] = 1

# dp 알고리즘
def do_dp(value) :
  for coin in pocket : 
    x = value - coin 
    if x < 1 : continue #0원 이하이면 제외 ( 화폐단위 X )
    d[value] = min(d[value],d[x]+1) #최솟값으로 테이블 저장

#호출
for i in range(1,m+1) :
  if d[i] > MAX : do_dp(i) #MAX보다 크면 아직 초기화가 되지 않음을 의미

#출력
if d[m] > MAX : print(-1)
else : print(d[m])

 

 

 

---

 

참고자료

이것이 취업을 위한 코딩 테스트다 with 파이썬 : 네이버 도서