hazxz   5달 전

DP[l][r][k]로 

3차원 DP를 사용하여 left ~ right 까지 k개의 집을 저장 한 뒤 오차의 합의 최소값.으로 정의 했습니다.

다른 분들은 DP[h][c]로 2차원 DP로 해결 하셨더라고요..

분명 그렇게 푸니 엄청 쉬운 문제였는데 저 혼자 괜히 돌아간 느낌이 강하긴 하지만


일단 f() 함수 안에서 이중 for문을 돌기도 하지만 결국 DP[200][200][200] 안에 모두 저장되있기 때문에

탐색노드는 최대 200*200*200 = 8백만 이라고 생각합니다. ( 분명 +오버헤드가 있겠죠..)

제 머리로는 8백만 정도면 돌아가지 않나 ? 싶은데 TLE가 뜨는건 f() 함수 안에서 이중 for문을 돌리는 오버헤드 + 재귀 함수로 구현했다는 점

이런 이유인걸까요 아니면 제가 시간복잡도를 잘 못 계산한 것일까요 ?? ㅜㅜ

etaehyun4   5달 전

생각하신 이유가 시간초과의 원인인게 맞는 것 같습니다.. 시간복잡도는 N^5인것 같네요

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