10803번 - 정사각형 만들기
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으로 풀면 안되는 문제인건가요 ㅜ.ㅜ?
시간복잡도가 N^2M이 나오기 때문에 시간 초과를 받게 됩니다.
채워야 하는 테이블의 개수는 N*M개 인데, 28번 줄에서 for를 i/2까지 돌아버리기 때문에 각각의 칸을 채우는 시간복잡도가 O(N)이 되어버립니다.
댓글을 작성하려면 로그인해야 합니다.
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으로 풀면 안되는 문제인건가요 ㅜ.ㅜ?