Coins

NOTE

블로그라기 보다는 생각나는 생각나는 대로 두서없이 적는 낙서장이라고 보면 될것 같다.

2019년 4월 17일 14:00~15:00

문제

1. 링크
2. Leet Code의 Coin Change 문제보다 더 어렵다.

생각 흐름

1. 처음에는 트리로 생각해서 각 노드는 잔돈의 종류만큼 자식 노드를 가지고 있다고 생각하고 Algorithm을 생각함.
2. 그런데 이 경우는 잔돈이 중복되는 경우에 대한 필터가 힘들었음.
3. 예를 들어서 아래의 예제에서 DFS로 10원으로만 계속 재귀로 차감하면서 파고 들어서 0원을 만드는 경우를 만든 하나의 경우, (10*11)
4. 올라오면서 50원이 됐을 때, 50원 짜리로 또 0원을 만드는 경우 (10*6+50)
5. 올라오면서 60~90원 때는 무시
6. 100원이 됐을 때, (10+50*2, 10+100)을 검출해낼 수 있어야했는데, 코드를 잘 짜기가 힘들었다.

   110 4
   10 50 100 500
   

7. 그래서 잔돈을 뜀뛰기로 생각함.
8. 바꾸고자하는 돈의 액수 + 1만큼 메모를 생성하고, 0인덱스는 1로 초기화
9. 그 안에서 잔돈액수만큼 뜀뛰면서 이전의 출발지점 값을 더해주는 것으로 생각함.
10. 위의 예로 봤을 때, 아래와 같이 된다.

    10
    i: 0 ... 10 ... 20 ... 50 ... 60 ... 110
    c: 1 ... 1  ... 1  ... 1  ... 1  ... 1
    50
    i: 0 ... 10 ... 20 ... 50 ... 60 ... 110
    c: 1 ... 1  ... 1  ... 2  ... 2  ... 3
    100
    i: 0 ... 10 ... 20 ... 50 ... 60 ... 110
    c: 1 ... 1  ... 1  ... 2  ... 2  ... 4