2294번 - 동전 2
안녕하세요.
해당 문제에서 가능한 k보다 큰 동전의 가치가 입력으로 주어지는 경우, 해당 동전은 k를 만드는 데 기여할 수 없으므로 입력 단계에서 무시하도록 처리했습니다.
그런데 이렇게 처리하니 메모리 초과 에러가 뜨는데 왜 그럴까요?
가능한 k보단 큰 동전 가치 입력을 무시하지 않고, dp 배열 크기를 10배로 키운 것은 오히려 메모리 초과가 뜨지 않고 ac를 받습니다.
메모리 초과: https://www.acmicpc.net/source...
맞았습니다: https://www.acmicpc.net/source...
혼자 생각해봐도 이유를 잘 모르겠어서 고수분들 도움을 구합니다.
입력으로
2 15
1 100000이 들어왔다고 가정해봅시다.
62번째 줄부터
in == 1일 경우에는 잘 작동하지만
in == 100000일 경우에는 coin[2] = 0이 되어버립니다.
dp_memoize 재귀호출 과정에서 coin[i] = 0인 사례가 있으면 자신을 다시 호출하기 때문에
무한 호출에 걸려 메모리 초과가 발생합니다.
댓글을 작성하려면 로그인해야 합니다.
suno 3년 전
안녕하세요.
해당 문제에서 가능한 k보다 큰 동전의 가치가 입력으로 주어지는 경우, 해당 동전은 k를 만드는 데 기여할 수 없으므로 입력 단계에서 무시하도록 처리했습니다.
그런데 이렇게 처리하니 메모리 초과 에러가 뜨는데 왜 그럴까요?
가능한 k보단 큰 동전 가치 입력을 무시하지 않고, dp 배열 크기를 10배로 키운 것은 오히려 메모리 초과가 뜨지 않고 ac를 받습니다.
메모리 초과: https://www.acmicpc.net/source...
맞았습니다: https://www.acmicpc.net/source...
혼자 생각해봐도 이유를 잘 모르겠어서 고수분들 도움을 구합니다.