[알고리즘 - dp] 동전 교환 문제

배운점
1.배열 -인덱스에 접근을 막기위해 if를 씀.
2.greedy, dp 둘다 알자.

서론
학교 수업에서  동전문제가 나왔습니다.
당연히 greedy겠구나 하고 풀고
별 생각 없었는데

1, 3, 4원일때 greedy가 실패함을 보게 되었습니다.
충격을 받고, dp 동전문제를 파보았습니다.

//참고
n을 이루는 최소 동전 갯수 문제입니다.




본론
재귀도 있지만, 보통 안쓰는 분위기니

1.for문과
2.사용한 최적 동전 수열 구하기
3. 경우의 수 모든 수열 구하기

이 3개가 메인인듯 보였고, 이를 조금 써보자 합니다.



풀 코딩은 손코딩으로 실컷 했기에 요점만 쓰겠습니다.


1 요점.
for 1~ N
  i = MAX
  for (coin : coins)
    if( i - coin >= 0)
       min(dp[i], dp[i-coin] +1
dp[n] 출력

2. 1의 과정에서 min의 조건을 if로 올리고
min바로밑에 first로 그 coin을 저장.

while(n>0)
arr.add(first (N))
N- FIRST(N)

arr출력

//휴대폰으로 쓰는게 상당히 힘들군요..

3.2중for문에
count( x )+= count (x-coin)
로 구하면 됩니다.



마무리
이를 공부하고 고민하며 손코딩한 사진들 올리며 마무리 하겠습니다.