코드업 KOI 문제 (DP) 문제집 올솔브

고등학교 때 처음 보고, 굉장히 오랫동안 풀고 싶어했던 문제들입니다.

https://www.acmicpc.net/problem/2625

2625번: DNA유사도

이 가혹한 문자열 문제에 가로막혀 오랫동안 생각하지 않고 있다가, 북마크를 보고 다시 떠올려 오늘 해결했습니다.

 

기본적으로 최장길이는 O(N^2K^2) dp를 통하여 LCS/편집거리와 비슷하게, 쉽게 구할 수 있다.

한  단계 발전시켜 한 방향으로 덱이나 누적합 등을 사용하면 O(N^2K)에 구할  수 있다.

다만 이제 역추적이 관건인데 여기서 dp에 문자열을 저장하면 문자열 최대 길이가 N/K이므로

O(N^3)이 된다.

여기서 두가지로 풀이가 갈리는데

하나는 dp는 거리를 저장하되, 추후에 역추적을 하는 풀이.

둘은 dp를 O(N^2)으로 최적화하고 문자열을 저장해 O(N^3/K)로 만드는 방법이다. 다만 K가 작아 O(N^3)이 되더라도 실제로 저장되는 문자열의 길이가 N보다 많이 작기 때문에 빠듯하게 통과한다.

 

난 두 번째로 했는데 2차원 덱 최적화 dp는 이게 처음이다. N<=5000,  0<=K<N, 역추적 없는 문제로 새로 만들 수 있겠다.

오랜 숙원을 없애버려 기분이 좋네요 ㅎㅎ!

https://codeup.kr/classop.php?class_id=7839