Dynamic Programming - 금화 모으기, 동전 거스름 돈

금화 모으기 - O(n²)

• 왼쪽 아래에서 오른쪽 위로 가면서 금화 모으기

Ceil(i, j) 는 (i, j) 일 때까지 오면서 모을 수 있는 최대 금화 개수
⇒ (i, j)의 바로 왼쪽과 바로 아래쪽 중 더 큰값이 정답. (집합 나누기)

Cell(i, j) = Max(Cell(i-1, j), Cell(i, j-1)) + Coin(i, j)

---

동전 거스름 돈

• N원을 1원, 4원, 6원을 사용하여 남김없이 거스름 돈 주는 방법.
• 만약 동전의 종류가 2배 이상 차이가 나면, 큰 것부터 주는 그리디 방법을 사용하면 되지만
  지금은 4원, 6원이 서로 2배이상 차이가 나지 않으므로 정답에 6원이 안들어갈 수도 있다.
  즉, 가장 큰 것부터 주는 것이 답이 아닐 수도 있음. 따라서 DP로 해결.

C[j] = j원을 거슬러 줄 때의 최적

1. j = 0
C[0] = 0

2. j > 0 & j < 4
1원만 사용하면 된다.
즉 현재 답은 1원을 한번 사용하고 나머지의 최적답
C[j] = C[j-1] + 1

3. j ≥ 4 & j < 6
- 1원을 한번 사용하고 나머지의 최적답
- 4원을 한번 사용하고 나머지의 최적답
중에 최소가 답이다.
C[j] = Min(C[j-1] + 1, C[j-4] + 1)

4. j ≥ 6
- 1원을 한번 사용하고 나머지의 최적답
- 4원을 한번 사용하고 나머지의 최적답
- 6원을 한번 사용하고 나머지의 최적답
중에 최소가 답이다.
C[j] = Min(C[j-1] + 1, C[j-4] + 1, C[j-6] + 1)