chatterboy   1년 전

c(i,j) = [i,j]에서 제거할 유전자의 최소 갯수라 하고 풀었습니다.

c(i,J) = c(i+1, j-1), if (dna[i] = 'a' and dna[j] = 't') or (dna[i] = 'g' and dna[j] = 'c')

c(i,j) = min{c(i+1,j)+1, c(i,j-1)+1, c(i,k) + c(k+1,j)} k = [i+1, j) otherwise

TLE인데 어떻게 줄일 수 있나요?

그리고 O(n^3)인줄 알았는데 반복적으로 바꾸는 과정에서 적어도 O(n^4)이 나오던데 잘 이해가 안되네요 ㅠ

케이스분류를 살살 해보시면 g가 가장 가까운 c와 매칭되었을 때만 체크해도(뒤쪽에 더 나오는 c를 무시해도) 최대값을 구할 수 있다는 것을 알 수가 있습니다.

모든 g,c / a,t pair에 대해 재귀호출을 하지 않고 각 g에서 오른쪽으로 가장 가까운 c, 각 a에서 오른쪽으로 가장 가까운 t 하나로만 재귀호출을 하게 바꾸시면 통과가 될거예요

chatterboy   1년 전

portableangel

그렇군요~ 신기하네요

답변 감사합니다

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