2157번 - 여행
이 문제가 dp풀이 방식인데,
n->1로 가는 방향으로 bfs로도 풀려서 소스를 짰는데 메모리 초과가 납니다.
최대 간선개수가 100000개라서
queue에다 pair로 최대로 넣어도 int 2개(8byte)*100000*(queue크기?) + vector pair로 선언한 int 2개(8byte)*300*(vector크기?)해도
메모리 256MB를 안넘을 것 같은데...메모리 초과가 납니다..
stl을 사용하면서 전부터 궁금했는데
stl queue나 vector 메모리 크기는 많이 더 큰건가요?
계산상에서부터 메모리가 부족한 경우가 아니라면 웬만해서 STL을 사용했다고 메모리가 초과하는일은 없습니다. 이 경우는 큐 최대 크기 계산이 잘못된것으로 보여집니다.
잘 생각해보시면 위 코드에서 큐에 들어가는 최대 크기는 간선개수보다 훨씬 많은 지수배만큼 증가하게 됩니다.
yukariko
아 그러네요!!! 제가 잘못계산했었네용 ㅜㅜ 감사합니다!
댓글을 작성하려면 로그인해야 합니다.
jh1125kr 7년 전
이 문제가 dp풀이 방식인데,
n->1로 가는 방향으로 bfs로도 풀려서 소스를 짰는데 메모리 초과가 납니다.
최대 간선개수가 100000개라서
queue에다 pair로 최대로 넣어도 int 2개(8byte)*100000*(queue크기?) + vector pair로 선언한 int 2개(8byte)*300*(vector크기?)해도
메모리 256MB를 안넘을 것 같은데...메모리 초과가 납니다..
stl을 사용하면서 전부터 궁금했는데
stl queue나 vector 메모리 크기는 많이 더 큰건가요?