13913번 - 숨바꼭질 4
안녕하세요.
ans에 자취를 기록하는 방법으로 풀어봤는데 메모리 초과가 나네요.
5 17의 경우
ans[5]에는 5
ans[4]에는 5 4
ans[8]에는 5 4 8
ans[16]에는 5 4 8 16
ans[17]에는 5 4 8 16 17
이런식으로 자취를 기록하도록 하고 큐에 넣을 때 체크하도록 했는데 메모리 초과가 어디서나는지 궁금합니다.
도움 주시면 감사하겠습니다.
자취를 전부 기록하면 O(N)개의 점 각각에 대해 길이 O(N)의 자취가 남으니까 O(N^2)의 메모리를 필요로 하게 되므로 당연히 메모리 초과입니다.
댓글을 작성하려면 로그인해야 합니다.
112ckek 4년 전
안녕하세요.
ans에 자취를 기록하는 방법으로 풀어봤는데 메모리 초과가 나네요.
5 17의 경우
ans[5]에는 5
ans[4]에는 5 4
ans[8]에는 5 4 8
ans[16]에는 5 4 8 16
ans[17]에는 5 4 8 16 17
이런식으로 자취를 기록하도록 하고 큐에 넣을 때 체크하도록 했는데 메모리 초과가 어디서나는지 궁금합니다.
도움 주시면 감사하겠습니다.