[ 알고리즘 ] 9. DP / Greedy 문제 풀기

 

칸 채우기

[ 값 채우는 Table , 어디에서 잘라야 Optimal인지 저장하는 Table 나눠야 함 ]

 

답 ▼

 

 

 

---

 

 

문제

: 동전 개수 최소화 하는 문제가 Greedy 알고리즘으로 안 될 수도 있다.

그런 경우를 제시해봐라.

 100보다 작은 값에, Coin 개수가 4개인 걸로.

 

▶ (영국 돈 단위) 잔돈은 30원인데 , 동전 단위는 {1,10,25}  일 때,

  ● Greedy 알고리즘 : 25 *1 + 1*5 = 6개

  ● DP 알고리즘 : 10 * 3 = 3개로 바로 끝남

 

 

DP 알고리즘으로 해서, 각 위치별로 동전 개수를 채워넣는다.

 

3,3을 보자.

▶ 3원을 거슬러 줘야 한다.

▶일단 뺄 수 있는 1원을 빼면 2가 남는다.

▶ 2원을 거슬러 줄 때 Optimal값을 사용한다.

   = 2 , 내가 뺐던 1원

   = 3개

 

 

근데 1,5,10 원 단위로 있으면 사실 1,2,3,4 > 1,2,3,4 ... 이런 식으로 감

 

---

 

 

▲ 결과로 나오는 식

 

 

(출처) 

한동대학교 용환기교수님 - 알고리즘