백준/DP
[코딩테스트] 9252번: LCS2
ydin
2022. 1. 9. 13:27
-문제: https://www.acmicpc.net/problem/9252
9252번: LCS 2
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
-정답풀이:
- findit()이 자기 이해가 잘 가지 않아서 복습해야할 것 같다
- lcs 값 구하는 것은 이해 완
-문제 이해:
- 왼쪽 (1,3)부터 오른쪽 아래로 1,2,3,4에 해당하는 문자들을 출력하면된다
- 근데 이거를 어떻게 구현하는지 잘 몰랐음
- 특정 인덱스의 왼쪽,위쪽 값을 비교해서 근방에서 최댓값이면 해당 문자를 넣고, 아니면 왼쪽이나 위로 움직이면 된다
