편집 시간: 2022년 3월 24일 오후 1:45

코드

Algorithm/9252.py at main · Junroot/Algorithm

풀이

기존의 LCS 문제에서 dp원리를 이해하면 쉽게 해결할 수 있다.

dp에 저장된 값을 보고 어떤 문자가 사용되었는지 확인하면되는데, 현재 위치에 저장된 값이 (왼쪽 위의 값) + 1인 순간이 해당 문자를 사용한 것이다.