suno   3년 전

안녕하세요.

해당 문제에서 가능한 k보다 큰 동전의 가치가 입력으로 주어지는 경우, 해당 동전은 k를 만드는 데 기여할 수 없으므로 입력 단계에서 무시하도록 처리했습니다.

그런데 이렇게 처리하니 메모리 초과 에러가 뜨는데 왜 그럴까요?

가능한 k보단 큰 동전 가치 입력을 무시하지 않고, dp 배열 크기를 10배로 키운 것은 오히려 메모리 초과가 뜨지 않고 ac를 받습니다.

메모리 초과: https://www.acmicpc.net/source...

맞았습니다: https://www.acmicpc.net/source...

혼자 생각해봐도 이유를 잘 모르겠어서 고수분들 도움을 구합니다.

39dll   3년 전

입력으로

2 15

1 100000이 들어왔다고 가정해봅시다.

62번째 줄부터

in == 1일 경우에는 잘 작동하지만

in == 100000일 경우에는 coin[2] = 0이 되어버립니다.

dp_memoize 재귀호출 과정에서 coin[i] = 0인 사례가 있으면 자신을 다시 호출하기 때문에

무한 호출에 걸려 메모리 초과가 발생합니다.

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