jujeongho   1년 전

O(mn 2^m)으로 풀었는데 당연히 시간 초과가 났고,

해설을 참고해봤지만, 아무리 생각해도 O(m 2^n)으로 푸는 방법을 모르겠어서 풀이에 대한 힌트를 여쭤봐도 될까요?!

cozyyg   1년 전

일반적으로 LCS를 구할 때 DP를 이용하는데, 완성된 DP 테이블이 어떤 특성을 가지고 있는지를 잘 생각해야 합니다. i번째 줄을 채울 때 i-1번째 줄의 값만 참고하기 때문에, 중간에 DP 테이블 상의 한 줄이 완전히 같아졌다면 함께 처리해줘도 된다는 게 가장 중요한 아이디어입니다.

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