lim551   2년 전

3차원 부분합 + binary search로 O(N + M^3logM)에 풀리는 문제인데, 정해와 같은 알고리즘을 썼는데도 불구하고 시간초과가 나서 질문드립니다.

정해에서는 3차원 부분합을 처리하는 부분에서 ps[x][y][z] = ps[x-1][y][z] + ps[x][y-1][z] + ... + ps[x-1][y-1][z-1]과 같이 직접적으로 코드에 데이터를 넣었고, 

저는 코드와 데이터를 분리해서 일관성이 있게 보이려고 위의 여러개의 +들을 dc배열로 표현해 나름 깔끔하게 구현하려고 했습니다. (실제로는 정해보다 더 더러워졌지만;;)

정해는 2500ms만에 AC가 뜨는 반면 제 코드는 첫 테케에서 TLE가 걸립니다. 저렇게 구현하는게 2배 이상의 시간차이나 날 정도로 비효율적일까요?

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