메모리초과는 거듭된 재귀로 인한 스택 메모리 초과로 보여지네요
저 소스를 고치는 방법은 잘 모르겠고..
DP 로 문제를 해결하고 싶으시다면 제가 사용한 방법을 말씀드리겠습니다.
(스스로 풀고 싶으시다면 안읽으셔도 좋습니다.)
먼저 1~K 원을 인덱스로 하는 배열을 잡습니다. (A[10001] 같이 되겠지요)
배열의 값에는 예를들어 A[i] 의 값은, 현재 가지고 있는 동전으로 i 원을 만들 수 있는 경우의 수가 들어가게 됩니다.
배열을 선언했다면 0으로 초기화 해주시고,
맨 처음 동전으로 만들 수 있는 모든 금액을 1씩 증가시킵니다.(0원도 포함)
첫 동전이 1원짜리면 1~K원 전부 1로 차게 되겠지요.
그 다음은 나머지 동전에 대해 현재 금액의 경우의 수를 각 동전을 더해 만들 수 있는 금액에 더해주는 과정을 해줍니다.
그렇게 끝까지 반복하면 A[k]의 값이 정답이 될겁니다.
힌트가 너무 많았나요?
저도 DP문제가 항상 어려워서 고민인데
이 문제를 해결하시면 동전2 문제나 7575번 앱 문제가 비슷하니 한번 풀어보시면 좋을겁니다 ㅎㅎ
skeksk91 9년 전
반복적 동적계획법을 연습하고싶은 한 청년입니다..
coin(has,now) // 가진돈이 has일 때 동전을 now번째 동전부터 사용해서 돈을 0으로 만드는 (동전을 다 쓰는) 경우의 수
이렇게하였지만 메모리초과로 실패합니다.
그렇다고 반복적 동적계획벅으로 바꾸기도 힘들었습니다.
제가 반복계획법에 많이 익숙하지않아서 그런건지.. 다른 분들은 잘만 사용하시는데 !!
고칠 수 있다면 어떻게 해야하는지 알고 싶습니다 ㅠㅠ