일단 dp 테이블을 다 채워놓은 다음에 i, j 에 있을떄 a[i]==b[j]이면 i-1, j-1로 가면서 i,j를 답에 포함시키구요 a[i]!=b[j]라면 dp[i][j] == dp[i-1][j] 일때 i-1, j로 또는 dp[i][j] == dp[i][j-1] 일때 i, j-1로 타고가면 될것 같네요
9252번 - LCS 2
일단 dp 테이블을 다 채워놓은 다음에 i, j 에 있을떄 a[i]==b[j]이면 i-1, j-1로 가면서 i,j를 답에 포함시키구요 a[i]!=b[j]라면 dp[i][j] == dp[i-1][j] 일때 i-1, j로 또는 dp[i][j] == dp[i][j-1] 일때 i, j-1로 타고가면 될것 같네요
그리고 처음에 제일 끝 글자부터 타고가시면 될거에요
댓글을 작성하려면 로그인해야 합니다.
junie 8년 전
LCS를 DP로 구하는 9251 (LCS1) 문제는 풀 수 있었습니다.
하지만 LCS를 재추적해서 실제 LCS를 출력하는 부분에서는 잘 모르겠더라구요..
여러가지 방법을 생각해 볼 수 있었습니다.
1. mem[i][j] > mem[i+1][j] && mem[i][j] > mem[i][j+1] 일 때 이 수가 LCS에 포함된다고 생각하기
반례 : abbbbb, baaaaa
2. mem[i][j] > mem[i+1][j+1]일 때 이 수가 LCS에 포함된다고 생각하기
반례 : friend, member
3. (아래에 나와있는 코드) i, j를 이동해가면서 a[i] == b[j] 일 때 이 수를 LCS에 포함시키기
반례 : 또다시 abbbbb, baaaaa
흐아...
어떻게 해야 LCS를 어떤 경우에서도 재구성해낼 수 있을까요?