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 메모리 크기는 많이 더 큰건가요?


yukariko   7년 전

계산상에서부터 메모리가 부족한 경우가 아니라면 웬만해서 STL을 사용했다고 메모리가 초과하는일은 없습니다. 이 경우는 큐 최대 크기 계산이 잘못된것으로 보여집니다.

잘 생각해보시면 위 코드에서 큐에 들어가는 최대 크기는 간선개수보다 훨씬 많은 지수배만큼 증가하게 됩니다.

jh1125kr   7년 전

yukariko

아 그러네요!!! 제가 잘못계산했었네용 ㅜㅜ 감사합니다!

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