-문제: 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에 해당하는 문자들을 출력하면된다
- 근데 이거를 어떻게 구현하는지 잘 몰랐음
- 특정 인덱스의 왼쪽,위쪽 값을 비교해서 근방에서 최댓값이면 해당 문자를 넣고, 아니면 왼쪽이나 위로 움직이면 된다
'백준 > DP' 카테고리의 다른 글
| [코딩테스트] 백준 11660번: 구간 합 구하기 5 (0) | 2022.01.10 |
|---|---|
| [코딩테스트] 백준 9184번: 신나는 함수 실행 (0) | 2022.01.10 |
| [코딩테스트] 2096번 : 내려가기 (0) | 2022.01.09 |
| [코딩테스트] 백준 1937번: 욕심쟁이 판다 (0) | 2022.01.07 |
| [코딩테스트] 백준 9655번: 돌게임 (0) | 2022.01.07 |