suminwow1   1년 전

다른분들의 풀이를 보면, 

현재 왼쪽 오른쪽 위치가 i, j라 하고, 둘의 숫자가 같은 경우 dp[i+1][j-1]가 팰린드롬인지 아닌지로 구성을 하는 것 같습니다. 

근데 제 코드의 21 ~ 25 위치에서, dp[i+1][j-1]을 보는 대신 나머지 그 가운데 부분을 직접 돌면서 팰린드롬인지 아닌지를 직접 판별하고 있습니다. 

그러면 N/2 이더라도, O(n^3) 이 나오고 시간초과가 될 줄 알았는데, 아닌 이유가 궁금합니다.

mythofys   1년 전

해당하는 알고리즘은 O(n^3 / 32) 정도에 동작하는 것으로 보입니다. 최악의 경우로는 0과 1이 n/2번 반복되는 경우 O(n^3)의 시간복잡도를 가지나, for문에서 1/4, 해당 데이터에서 0과 1이 반복되므로 1/2의 경우에만 k를 변수로 사용하는 for문에 접근하고, 각 인덱스에 접근하는 횟수가 (2 + 4 + 6 + 8 + ... + n) = n(n+2)/4로 상수가 상당히 작아서 제한조건에 걸리지 않고 통과하는 것으로 보입니다. 해당 데이터를 추가하는 것이 유의미할지 모르겠네요.

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