sambongdj   3년 전

문제 풀이법대로 이전 M+1만큼 비트마스크에 저장, 메모이제이션해서 문제를 풀려고 했고 예제도 다 나왔습니다.
17 17에서 시간초과가 뜨는 것 알고 있습니다.
하지만 어떻게 해결할지 감이 안옵니다!!
도와주십쇼..

ntopia   3년 전

아무래도 재귀 DP 라 상수가 커져서 그런 것 같은데

반복문 형식으로 바꿔보시겠어요?

doju   3년 전

메모이제이션 방식의 DP는 함수를 호출하고 값을 반환하는 과정이 추가로 들어가므로 반복문 DP에 비해 다소 느립니다. 게다가 이 문제는 상태 공간이 상당히 크기 때문에 그 차이가 더욱 커질 수 있습니다.

또 다른 문제는 배열을 참조하는 방식입니다. 이 코드는 보통 [nbm][leave - 1][nbm | (1 << m)][leave - 1] 을 연속으로 참조하게 되는데, 두 주소가 아주 멀리 떨어져 있기 때문에 참조에 시간이 오래 걸립니다.

출제진은 일반적인 반복문 DP 풀이의 수행 시간의 약 4배를 제한 시간으로 설정했고, 메모이제이션을 사용하더라도 배열을 [N × M][bitmask] 순서로 선언할 경우 좀 빠듯하지만 AC를 받을 수 있었습니다. 이 코드는 위의 두 가지 비효율이 겹쳐 출제진 풀이의 약 7배의 시간이 걸리는데, 시간 제한을 늘려야 할지는 좀 생각해 보겠습니다.

sambongdj   3년 전

변수 위치를 변경하니  AC가 나왔습니다. 신기하네요...

반복문 형식으로 어떻게 짜는지는 감이 안오네요ㅠㅠ

무튼 감사합니당~

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