BOJ 9084 - 동전

문제 링크(Link)

---

https://www.acmicpc.net/problem/9084

문제 해결(Solution)

---

 DP로 문제를 해결한다

 1. DP[n][m] : n번 째로 입력받은 동전에서 금액이 m일 때의 방법의 수 (TOP-DOWN)

 2. DP[m] : 금액이 m일 때의 방법의 수 (BOTTOM-UP)

주의할 점 || 생각해볼 점(Caution || Consideration)

---

 1. 왜 TOP-DOWN 방식과 BOTTOM-UP 방식일 때의 DP table의 차원 수가 다를까?

  : BOTTOM-UP 방식일 때는 이중 for loop을 사용해서 동전 조합의 중복을 막을 수 있지만, TOP-DOWN 방식은 동전 조합의 중복을 막기 위해선 입력받은 동전의 순서를 저장해야한다. 그러므로 TOP-DOWN의 DP table의 차원 수가 더 크다. 

 2. 시간 복잡도는 얼마나 차이가 날까? 

  :  배열의 차원이 다르지만 BOTTOM-UP 또한 이중 for loop를 사용하므로 시간 복잡도 O(NM)이 된다. 그러므로 동전 문제는 어느 방법으로 해결하든 상관없다!

참고(Reference)

---

 - 

※ 정확하고 부드러운 태클은 언제나 환영입니다.