thkighie1224   8년 전

Memorization 으로 풀었는데요 ㅜ.ㅜ

시간 초과가 뜨네요...

가로 7 세로 3 인 경우

Cache[7][3] = (Cache[6][3]+Cache[1][3]) , (Cache[5][3]+Cache[2][3]) , (Cache[4][3]+Cache[3][3]) , (Cache[7][1]+Cache[7][2]) 중에서 작은 걸 고르는 식으로 계산 했습니다.

위와 같이 모든 경우를 다 계산 할 필요가 없는 문제인가요? 아니면 Memorization으로 풀면 안되는 문제인건가요 ㅜ.ㅜ?

baekjoon   8년 전

시간복잡도가 N^2M이 나오기 때문에 시간 초과를 받게 됩니다.

채워야 하는 테이블의 개수는 N*M개 인데, 28번 줄에서 for를 i/2까지 돌아버리기 때문에 각각의 칸을 채우는 시간복잡도가 O(N)이 되어버립니다.


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