여러가지 시행착오가 있었던 문제였다. 각각의 동전을 이용하여 K만큼의 값이 나올수 있는 경우의 수를 구하면 되는 문제이다. 동전의 구성은 같지만 순서는 다른것도 포함될수있다는 말에 여러가지를 생각했는데 처음 생각했던것은 Permutation 방식이었다.
테스트케이스 까지는 통과했지만 아쉽게도 시간초과가 나왔고 자세히 보니깐 K의 값이 10^4 다. 이 많은 계산을 Permutation으로 구할려했기때문에 시간초과가 나오는것은 너무 당연했기에 내가 예전에 풀었던 Memoization 방법을 활용한 Coin Change 방법을 사용하기로 했다.
이번에는 메모리 초과가 나왔다. 다시 보니 N의 최대 길이는 100이나 된다. Coin Change 에선느 13의 최대길이로 구하는 거였기에 각 index 마다 구할수있는 값을 저장해서 써볼수 있었지만 이런 문제 같은 경우는 100개가 될수있는 index에서 10^4 값이 되는 K개의 값을 저장해야 했기때문에 시간초과는 통과 할수있어도 메모리 적인 부분에서 너무 컸던거같다.
그래서 DP에서 쓰이는 다른 방법인 Tabulation 방법을 쓰기로했고 난 지금까지 DP문제를 풀때 Memoization 방법만을 고집해왔기때문에 좀 처음부터 다시 찾아봤었다.
생각하던중 내 기본이 될수있을것만 같았던 Climbing Stairs 를 다시 풀어보기로 마음 먹었다.
예전에도 포스팅을 해봤던 문제였는데 Climbing Stairs 문제는 계단을 한개 혹은 두개까지 오를 수있고 n만큼의 계단을 오르게 위한 모든 경우의 수를 리턴하는 문제였다. 그리고 구현하기 위해서는 DP 테이블을 만든다음에 DP[0] 과 DP[1] 을 1로 설정해주었다. 이유는 0개의 계단을 오르기 위해선 아무것도 안하므로 1개의 방법이 있고 1개의 계단을 오르기 위해서는 계단 하나를 밟는 1의 방법이 있기 때문이였다. 이런 식으로 DP 테이블에 모든 경우의 수를 담아두면은 우리가 원하는 해당 N만큼 갔을때 저장되있는 모든 경우의 수를 찾아 더해주면 됐었다.
다시 돌아와서 왜 이 문제를 동전 1 문제를 푸는데 적었냐고 하면 꽤 비슷한 원리이기 때문이다.
우리는 코인 벡터에 코인을 담아서 사용할수있는 코인만 이용해 탐색을 할것이다. 그리고 사용할수 있는 코인만을 이용해서 K값까지 만들수있는 모든 조합을 만들것이다. 그렇게 되면 위에 있는 Climbing Stairs 와 같은 원리로 해당 K에 우리가 현재 가지고 있는 코인들로 만들수있는 모든 조합들을 더하고 그곳에 속해있는 값을 DP테이블에 저장한다음에 꺼내서 쓸수있다.
설명이 말로만 하면은 좀 헷갈릴수도 있기때문에
https://yabmoons.tistory.com/491
얍문님의 블로그를 또 참조해서 설명을 다시 나열했다. 굉장히 많은 도움을 받는 블로그 같다. 그 외에도 DP에 대한 이해도를 높이기 위해 항상 고집하던 Memoization 방식을 내려놓고 Tabulation 방법을 적극적으로 사용해야겠다. 그러기 위해서는 Table 을 이용한 Knapsack 이론도 다시 보고
https://leetcode.com/discuss/interview-question/1380561/Template-For-Dynamic-programming
리트코드에 있는 이런 좋은 링크또한 사용해서 공부해야겠다.
배운점:
1. DP 테이블을 통한 Visualization
2. Tabulation DP 방법
