저번에 풀었던 동전 1 문제에서 다이나믹 프로그래밍에 대한 Tabulation 이해도를 높혔었다. 그리고 이번에 다시 풀어보는 동전 2 문제는 동전 1 문제와는 다르게 최소한의 동전 "개수" 를 이용하여 K원을 만들어야한다. 동전 1 문제에서는 K원을 만들수 있는 동전의 모든 경우의 수를 출력하라고 했던 점을 비교하면 동전 2는 비슷하면서도 많이 다른 유형의 문제라는걸 알수있다. 사실 이런 유형의 문제는 이미 리트코드에서 Coin Change 문제로 Memoization 을 사용하여 풀었던 기억이 있지만 리트코드에서 풀었던 문제는 상대적으로 쓸수있는 동전의 크기가 많이 작았었다. 그렇지면 여기서는 최대 100가지의 코인을 사용할수있고 일반적인 Memoization 방식을 쓰게된다면 또 메모리 에러가 나올수있기에 Tabulation 방법을 선택했다.
다이나믹 프로그래밍은 글자로 설명하려고 하면 많이 힘든거같다. 이번 문제를 풀면서도 실제로 내 개인 노트북에다가 그림을 그려가면서 그 원리를 이해하려고 했었다. 그 결과, 이 문제는 동전1 과는 다르게 최소한의 개수를 구하기 위해서는 내가 지금 가지고 있는 코인들과 K만큼의 값을 얻기 위해 써야하는 코인에 차이를 잘 이해했어야했다.
가장 먼저 DP 테이블을 만들어준 다음에 1부터 시작해서 K만큼의 액수까지 값을 INF 로 지정해주었다. 이건 초기화 단계라고 생각하면 될거같다. 그 후에는 코인에 들어있는 코인의 해당 액수에는 1이라고 설정해준다. 왜냐면은 만약 K만큼의 값이 우리가 가진 코인 하나의 값으로 채울수있다면 1이 최소의 코인이기 때문이다.
그 다음 단계로는 동전 1에 문제와 똑같이 코인지갑을 탐색해주면서 K 만큼의 해당값까지 루핑을 해준다. 그리고 루핑이 계속 진행이 될수록 그림을 그리면 더 이해하기 쉬울텐데 현재 유지하고 있는 모든 DP 에는 지금 지갑에 있는 동전들로 만들수 있는 최소한의 코인을 저장했다. 그렇기 때문에 지갑을 루핑하면서 만약에 이전에 있던 코인을 써야한다면 +1 을 해주면서 최소한의 동전을 구할수있다.
설명이 솔직히 부실했는데 더 많은 설명은 동전 1에 걸어두었던 디피 템플릿을 참고하고 얍문님의 블로그를 보는게 맞는거같다
배운점:
1. DP 테이블 활용법
2. INT_MAX 보다 INF 를 define 해주는게 맞을때도 있다.
