플레 스트릭 잇기 + 랭작을 위해서 푼 문제입니다.

문제를 처음 봤을 때는 입력 문자열을 전부 삭제하지 않아도 된다고 생각해서

aaazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzaaa
aaaa

의 경우

c a
c a
c a
a a

가 최적인 것으로 잘못 이해했었는데, 알고 보니 전부 삭제해야 하는 거였더라고요..

처음에는 LCS를 구한 후 해당하는 글자들은 복사하고 아니면 추가 / 삭제 / 수정을 적절히 하게끔 구현했는데, 7%에서 WA를 받았습니다.

반례를 찾다가,

wacluehilwae
awbrkje

이런 경우에는 LCS를 전부 복사하는 것보다 a와 e만 복사하고 나머지는 삭제 / 수정으로 처리하는 게 이득이라는 사실을 발견했습니다.

그래서 히르쉬버그를 LCS를 구하는 데에만 쓰는 게 아니라 응용해서 사용해야 된다는 걸 드디어 깨달았고, 코드를 갈아엎었습니다.

LCS 문제에서 $dp[i][j] = max(dp[i-1][j-1] + (s1[i]==s2[i]), dp[i-1][j], dp[i][j-1])$이었던 dp 식을 $dp[i][j] = min(dp[i-1][j-1] + (s1[i] \neq s2[i]), dp[i-1][j] + 1, dp[i][j-1]+1)$으로 수정하고, LCS를 리턴하는 대신 출력을 적절히 하도록 코드를 짰습니다.

말은 적절히 한다고 했지만 꽤 많이 어려웠고요, 저 반례가 키보드로 아무거나 친 건데 엄청나게 큰 도움이 됐습니다. 구현 방법은 다음과 같습니다:

s1을 세로, s2를 가로로 두고 s1의 길이가 1이 될 때까지 반으로 나눕시다. 그 후 len(s1)==1 이 됐으면, len(s2)==0인 경우 s1을 지우고, s1과 s2에 공통된 문자가 있으면 그 문자를 복사하고, 없으면 아무 문자나 하나 골라서 수정을 하면 됩니다. (나머지 len(s2)-1 개의 문자는 추가 연산으로 처리)

기여를 보니까 다들 LCS 5와 비슷한 난이도라고 생각하시는 거 같은데, 저는 이상하게도 LCS 5는 구현이 쉽게 됐는데 이 문제는 구현에만 2시간 넘게 썼네요 :blobsad: