skeksk91   2년 전

반복적 동적계획법을 연습하고싶은 한 청년입니다..

coin(has,now)  // 가진돈이 has일 때 동전을 now번째 동전부터 사용해서 돈을 0으로 만드는 (동전을 다 쓰는) 경우의 수

이렇게하였지만 메모리초과로 실패합니다.

그렇다고 반복적 동적계획벅으로 바꾸기도 힘들었습니다.

제가 반복계획법에 많이 익숙하지않아서 그런건지.. 다른 분들은 잘만 사용하시는데 !!

고칠 수 있다면 어떻게 해야하는지 알고 싶습니다 ㅠㅠ

yukariko   2년 전

메모리초과는 거듭된 재귀로 인한 스택 메모리 초과로 보여지네요

저 소스를 고치는 방법은 잘 모르겠고..

DP 로 문제를 해결하고 싶으시다면 제가 사용한 방법을 말씀드리겠습니다.

(스스로 풀고 싶으시다면 안읽으셔도 좋습니다.)

먼저 1~K 원을 인덱스로 하는 배열을 잡습니다. (A[10001] 같이 되겠지요)

배열의 값에는 예를들어 A[i] 의 값은, 현재 가지고 있는 동전으로 i 원을 만들 수 있는 경우의 수가 들어가게 됩니다.

배열을 선언했다면 0으로 초기화 해주시고,

맨 처음 동전으로 만들 수 있는 모든 금액을 1씩 증가시킵니다.(0원도 포함)

첫 동전이 1원짜리면 1~K원 전부 1로 차게 되겠지요.

그 다음은 나머지 동전에 대해 현재 금액의 경우의 수를 각 동전을 더해 만들 수 있는 금액에 더해주는 과정을 해줍니다.

그렇게 끝까지 반복하면 A[k]의 값이 정답이 될겁니다.

힌트가 너무 많았나요?

저도 DP문제가 항상 어려워서 고민인데

이 문제를 해결하시면 동전2 문제나 7575번 앱 문제가 비슷하니 한번 풀어보시면 좋을겁니다 ㅎㅎ

skeksk91   2년 전

힌트 많이 주셔서 고맙습니다 ㅠㅠ 

감동받아서 가슴 한켠이 따뜻해졌습니다. 감사합니다..

말씀하신거 읽어보고 성공하믄 동전2나 7575풀어봐야겠네요 ㅎㅎㅎ!

yukariko   2년 전

에고 7575번이 아니라 7579번이네요 ㅋㅋ

어찌됬든 도움이 되셔서 다행입니다.

myungwoo   2년 전

제 생각에는 스택 메모리 초과가 뿐만 아니라, cache[10001][101] 부분이 3.8MB 가량 잡아먹어 기타 헤더파일을 포함해서 메모리 초과가 난 것 같습니다.

생각해보면 뒤에 101 부분을 잡을 필요가 없습니다. 메모리를 cache[10001]로 잡아서 해결하시면 됩니다.

재귀호출을 하지 마시고, 이중 for문으로 DP를 수정하시고, 배열 또한 작게 잡으시면 무난하게 해결할 수 있을겁니다.

skeksk91   2년 전

@

myungwoo 예리한 분석 감사합니다. ㄷㄷ 

참고해서 풀어보겠습니다

chatterboy   2년 전

https://www.acmicpc.net/board/view/322

도움이 되실지 모르겠지만 같은 문제에 대한 질문글입니다.

댓글을 작성하려면 로그인해야 합니다.