zpapl   6년 전

제 소스는 9%에서 메모리 초과가 발생합니다.

다른 사람의 풀이를 참고했을 때(http://wootool.tistory.com/175)

저와 비슷하게 dp[N][3]으로 사이즈를 잡았는데 다른 점은 위의 분은 입력 값을 따로 저장하지 않았다는 것?

제 생각으로는 제 코드도 4MB 미만인 것 같은데 왜 안될까요??

djm03178   6년 전

이 문제는 원래 입력을 전부 받아놓지 않고 풀기를 바라는 문제인데, 제한이 약해서 이런 방법으로도 통과가 될 수 있을 뿐입니다. vector의 경우 메타데이터들이 일부 필요하기 때문에 단순 int 배열에 비해서 메모리를 많이 먹으며, 약간의 차이로도 메모리 초과가 발생할 수 있습니다. 또한 dfs 함수가 재귀호출을 하면서 호출 스택이 쌓이므로 그 부분에서도 메모리가 늘어납니다.

그리고 입력 방법도 잘못되었습니다.51번째 줄은 j < 3이어야 합니다.

jh05013   6년 전

링크하신 코드는 3460KB를 사용해서 간신히 통과됩니다. 정확히 재 보지 않았지만 이 코드는 더 무거워 보입니다.

zpapl   6년 전

이 문제는 top-down 방식에는 부적합한가요?

djm03178   6년 전

말씀드렸다시피, 애초에 입력을 다 받아놓고 전체를 dp할 필요도 없는 문제입니다. top-down이면 피할 수 없죠. bottom-up으로 하면, 딱 한 줄 씩만 입력받고 계산하고를 반복할 수 있어 메모리가 O(1)밖에 필요하지 않습니다.

zpapl   6년 전

항상 제 질문에 답변은 djm님이네요 ㅋㅋ

항상 감사드립니다. 풀이 방법을 알 것 같네요.

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