풀 소스코드를 보여주시지..
풀 소스를 보니 k는 동전 가짓수와 관련된 변수고.. total은 만들어야 하는 금액이 아닐까 싶네요.
이걸 재귀로 푸셨다는 건데. (잘 겹치치 않는) 문제에 있는 예제 말고 조금 극단적인 케이스를 넣어볼게요.
총 금액은 20이네요. 그리고 wj님 소스코드상으로 보면 dfs에 이렇게 들어갑니다.
dp(100, 5) = dp(100, 4) + dp(99, 4) + ... + dp (90, 4)
그리고 2원짜리 동전까지 고려해 봅시다.
dp(100, 4) = dp(100, 3) + dp(98, 3) + ... + dp(80, 3)
dp(99, 4) = dp(99,3) + dp(97, 3) + dp (95, 3) + ... + dp(79, 3)
dp(98, 4) = dp(98,3) + ...
중복이 되고 있지요? 마치 피보나치 함수를 재귀로 푸는 것과 같죠.
만약 dp(98, 3)의 값을 저장해 놓았다면 다시 dp(98, 3)을 계산할 필요가 없을 겁니다. 막바로 끝나겠죠.
하지만 그렇지 않다면 다시 재귀호출 하면서 max값을 구하고 리턴할 겁니다. 시간 차이가 꽤 많이 나죠..
wjddms206 6년 전
아주 기초적인 질문일 수도 있는데요.. 고수님들 제발 dp초보를 도와주세요.
저는 이 문제를 재귀+메모이제이션으로 풀었습니다. 맞긴했습니다. 근데 제대로 알고푼것 같진 않습니다 ㅠㅠ
물론, 반복적인 작업을 줄이려고 메모이제이션을 쓴다는 것은 압니다.. 하지만
이런 문제와 같은 경우에 왜 꼭 메모이제이션으로 풀어야 할 이유가 있나요?
제 코드의 11, 14, 17번째 줄과 같이 굳이 메모이제이션 안쓰고 재귀로만 풀어도 되지 않나요?
이 문제의 예로는 dp를 사용하나 재귀로만 푸나 똑같은 작업횟수입니다.
설명 혹은 반례라도 알려주실 수 있으실까요?