다른 풀이 문의

정말 쉽게 풀어보는 코딩 테스트 top 기본 문제 (with 자바)

Coin Change

작성

152

엄청 싼티나게

배열을 reverse로 정렬해서

while문을 돌면서 나가는 조건은 coin들을 큰것부터 빼면서 최종금액이 0이 되는 경우로 하고

큰 코인부터 *를 늘려나가면서 기존 원금에서 - 해나가면서 하나씩 작은 코인으로 옮겨가면 가장 최소개의 코인으로 결과가 나올텐데요

이렇게하면 난이도가 확 낮아지죠. 근데 dp로 해야하는 이유가 무엇인지, (코딩테스트에서 더 점수를 많이 받을거라 생각되는데 - 그렇다면 물론 이것만으로도 이유는 끝이지만,, 이걸 공부하는 이유가 그것때문이니.. - 그게 아닌 다른이유도있을까요?) 궁금합니다.

답변 2

질문자

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

지식공유자

안녕하세요

열공하시는군요 ~~
맞습니다 님이 생각하신거처럼 해보세요요그리고 코딩을해보세요 그게 가장 나다운 코딩이고 거기서부터 생각이 발전합니다

이문제를 풀면 그렇게 푸는게 맞습니다

문제는 그렇게 되면 나중에 메모리 부족 같은 현상(tle ,time limited exceeded)가 발생하고 아 이렇게 하면 안되겠구나 하게됩니다

그래서 for문 두번 돌릴때 한번 거치거나 거칠필요가 없는 애들을 건너 뛰게 만들죠,재사용이라고하고 dynamic programming dp라고 하고 그 규칙을 찾아냅니다

이런식으로 시간을 많이 투자하셔서 풀면 dp 문제에 대한 감이 오죠 dp는 하방 상방있습니다 topdown bottomup방식 구미에 맞게 구현하면 되겠죠~

인프런 커뮤니티 질문&답변