알고리즘23-2 동전 교환

 

 

---

다이나믹 프로그래밍 적용 후) O(W N)

 

동전 갯수를 가장 적게쓰는 방법을 쓴다. 

 

하나로 못만드는 금액이면 여러개로 만들어야하는데, 

이미 가능한 금액에 2원 or 5원 or 9원을 추가해야한다.

 

마지막에 추가한 것은 2,5,9원 중 하나일 것이다.

마지막에 2원을 추가해서 3를 만들수있나? 없다.

마지막에 5원을 추가해서 3를 만들수있나? 없다.

마지막에 9원을 추가해서 3를 만들수있나? 없다.

 

 

하나의 값을 계산하는데 n개를 본다.

0,1,2,...,w 

= O(WN)

 

 

---

---

막대기 자르기

 

n-1번 자르므로 2^(n-1)가지

 

 

?

다 해보는 것: O(2^(n-1 x n))

다이나믹 프로그래밍 : O(nk)

 

동전 나누기와 아이디어 자체는 비슷하다.

 

---

---

합 분해

 

k=2 n=20

순서가 다른 것을 따로 센다.

순서를 무시하게 되면 훨씬 어려운 문제가 된다.

 

2개로 0,1,2,3을 만드는 방법을 안다고 치자

 

 

 

 

3개로 2를 만든다고 치면

2개로 0을 만드는 것 +2

2개로 1을 만드는 것 +1

2개로 2를 만드는 것 +0

 

 

 

 

한 칸 계산할때 앞에 줄을 다 본다.

O(n^2 k) => 

 

조금 더 생각해보니까 줄일 수 있었음