글 읽기 - LCS를 2회 하는것과 3차원 DP의 차이점

A문자열 B문자열을 LCS를 하여

LCS결과문자열인 Temp 문자열을 구하고

Temp 문자열을 C문자열과 LCS를 하여

최종 결과물을 구하였습니다.

틀렸다고 하더군요...

이후에 3차원 배열로 DP로 풀긴하였는데

Temp문자열을 쓰는 방법이 틀린 이유가 무엇일까요?

1. 방법은 맞지만, 구현이 잘못되었다. (코딩실수)

2. 접근 방법 자체가 잘못되었다. (예외 사항이 있다)

아쉽게도 2입니다. 반례를 금방 생각할 수 있죠:

A: dababcf
B: ababdef
C: df

LCS(A,B): ababf
LCS(LCS(A,B),C): f
LCS(A,B,C): df

아... 완벽한 이해는 아니지만 느낌은 왔습니다.

가장 길이가 긴 것을 끌어내기에 틀리게 되는것 같네요;;

감사합니다.

게다가 해가 유일하지 않음도 한 몫을 합니다...

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

Baekjoon Online Judge