BOJ 4781 사탕 가게

01 knapsack 문제 같아 보인다...
d[n][m] = n번째 사탕을 살펴보면서, 돈은 m원 남아있을 때, 구매할 수 있는 가장 높은 칼로리 로 두고 풀어봐야겠다. 음 근데 좀 다른 것이 사탕의 개수는 여러개라서 몇 개든 살 수 있다. 그래서 for문을 넣어서 n번째 사탕을 볼 때, 구매 안하는 경우, 1개 구매하는경우, 2개, 3개... 구매할 수 있는데 까지 다 구매해보는 경우로 해보려고 한다. 음 근데 그러면 시간 복잡도가 O(n*m*m) 이 될 것 같은데... m은 100.00이라서 계산을 편하게 하기 위해 100을 곱해서 10000으로 쓰고 있다... 일단 한 번 풀어봐야겠다. 음 메모리 초과가 났다. 재귀함수를 많이 호출하게 되니 그런 것 같다. 확실히 이렇게 하는 건 무리다.

질문 게시판을 보고 하니 일차원 배열로 하는 게 가능해 보인다. 그래서 한 번 1차원 배열로 생각해보려고 한다. (갑자기 느낀건데, 잘 기억은 안나지만 이차원 배열에서 일차원 배열로 줄이는 것이 BOJ 2176 합분해 문제와 뭔가 유사한 느낌이 든다. 꼭 다시 풀어보고 정리하자.) d[m]=돈이 m원 남아있을 때, 구매할 수 있는 가장 높은 칼로리 로 두고, n개의 사탕에 대해 일일이...음 sorting을 하면 어떨까? 큰 순서대로 즉 내림차순으로 sorting을 해두고 m보다 가격이 작은 사탕에 대해서만 보면 좀 더 좋을 것 같다. 한 번 짜봐야겠다.
-> 짜봤는데 짜다보니 배열만 일차원 배열 썼을 뿐 뭔가 아까랑 비슷하다... 그리고 결국 25퍼센트에서 시간초과가 나버렸다... 이번에 짠 방식도 결국 시간 복잡도는 아까와 똑같기 때문에... 혹시나 해서 sorting을 주석처리 했는데 역시 시간초과... 다른 방법이 필요하다.

아... 갑자기 생각났는데.. 동전 문제와 비슷해보인다. 동전 2 문제 였나? 거의 똑같아 보이기도 한다...음 동전 금액이 칼로리, 동전 개수가 금액... 좀 충격적이다. 이걸 이제야 깨닫다니

몇가지 실수한 끝에 AC를 받았다. 정말 동전 문제랑 똑같다...그럼에도 생각하지 못한 것과풀이는 그대로고 말만 바뀌었는데도 동전 문제랑 같다는 것을 알고도 제대로 풀이를 도출해내지 못했다. 나는 그냥 동전 문제를 외우고 있었던 걸까...  음 반성하게 되는 계기가 되었고 좋은 문제였다...

d[m]=돈 m원으로 구매할 수 잇는 가장 높은 칼로리
d[m]=MAX(i=0~n) [ d[m-candy[i].price]+candy[i].calory ]