다른 풀이 문의

Question

엄청 싼티나게 배열을 reverse로 정렬해서 while문을 돌면서  나가는 조건은 coin들을 큰것부터 빼면서 최종금액이 0이  되는 경우로 하고 큰 코인부터 *를 늘려나가면서 기존 원금에서 - 해나가면서 하나씩 작은 코인으로 옮겨가면 가장 최소개의 코인으로 결과가 나올텐데요 이렇게하면 난이도가 확 낮아지죠. 근데 dp로 해야하는 이유가 무엇인지, (코딩테스트에서 더 점수를 많이 받을거라 생각되는데 - 그렇다면 물론 이것만으로도 이유는 끝이지만,, 이걸 공부하는 이유가 그것때문이니.. -  그게 아닌 다른이유도있을까요?)  궁금합니다.

BeginnerCoder · Answer

제방식대로 풀려도, 경우의 수가 많아질 경우 메모리 부족이 발생할 가능성이 있으므로 당장 코테에서 되더라도 좋은 점수는 못받겠네요 . 조언감사합니다. dp 어렵네요 ㅎㅎ

푸샵맨 코딩스터디 · Answer

안녕하세요  열공하시는군요 ~~ 맞습니다 님이 생각하신거처럼 해보세요요그리고 코딩을해보세요 그게 가장 나다운 코딩이고 거기서부터 생각이 발전합니다 이문제를 풀면 그렇게 푸는게 맞습니다  문제는 그렇게 되면 나중에 메모리 부족 같은 현상(tle ,time limited exceeded)가 발생하고 아 이렇게 하면 안되겠구나 하게됩니다 그래서 for문 두번 돌릴때 한번 거치거나 거칠필요가 없는 애들을 건너 뛰게 만들죠,재사용이라고하고 dynamic programming  dp라고 하고 그 규칙을 찾아냅니다  이런식으로 시간을 많이 투자하셔서 풀면 dp 문제에 대한 감이 오죠 dp는 하방 상방있습니다 topdown bottomup방식 구미에 맞게 구현하면 되겠죠~