우선 코드 수정 전의 calcError와 getMinError의 시간복잡도는 각각 O(N^3)으로, 둘을 같이 적용해도 똑같은 O(N^3) 코드입니다.
시간초과가 난 이유는 double형의 느린 연산 속도,
200 * 200 * 200 배열의 낮은 지역성으로 인한 캐시 효율 감소
여러개의 테스트케이스
가 원인으로 생각됩니다.
참고로 말씀드리자면 현재 코드는 조금 위험한 코드입니다.
그 이유는 cache에 here, there, _c가 담기지 않고 here이 빠지게 되었는데,
이것이 제대로된 중복처리를 할 수 없기 때문입니다.
1 0 1 일때의 답과 100 0 1일때의 답은 달라야하는데
there과 _c가 똑같은 0 1 이므로 둘은 같은 값을 가지게 됩니다.
실제로 return 위에 ret = 0; 같은 코드를 추가하게 되면 이 코드는 틀리게됩니다.
다만 의도하신건지는 모르겠지만 점화식의 특수성으로 인해 위 코드가 오답을 내진 않을것같습니다.
dkwkekzz 7년 전
안녕하세요. 일단 제 글을 읽어주셔서 감사합니다.
이해가 안 되는 부분이 있어 질문드리려고 합니다.
아래 코드와 같습니다.
꽤 많은 시도를 거쳐 성공했는데요.
처음에 시도한 코드는 cache에 here을 추가하였습니다.
물론 캐시의 양이 줄면 시간복잡도가 줄겠지요.
하지만 이 문제에서 입력 상한은 200이며 200*200*200은 시간내에 계산할 수 있는 양입니다.
문제가 될 수 있는 부분은 calcError이며 이 부분을 질문드리려 합니다.
시간 초과가 된다는 의미는 calcError에서의 시간 복잡도가 합쳐져 200^3 * 200^3? 모르겠습니다.
그런데 이건 있을 수 없지요. getMinError에서 calcError를 호출하긴 하지만 getMinError의 모든 부분 함수에 대하여 200^3만큼의 연산을 하는건 아니잖아요. 캐시로 인하여 결국에 모든 연산은 200^3내로 이루어질 것 같은 것이 제 생각입니다.
혹시 어떤 부분이 오류인지 알고 계신다면 답변 꼭 부탁드립니다.
감사합니다.