728x90
https://www.acmicpc.net/problem/9252
9252번: LCS 2
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
이전에 LCS문제를 풀어봤다면 비슷하게 풀 수 있다.
해당 예제를 dp에 넣을때 위처럼 쌓여지게 된다.
첫째줄부터 살펴보면 C를 가지고 A, AC , ACA, ACAY, ACAYK, ACAYKP 랑 순서대로 비교하면서 배열을 찾는 것이다.
두번재줄은 A,C를 가지고 A, AC , ACA, ACAY, ACAYK, ACAYKP 랑 비교하면서 길이를 찾는다.
반복하다보면 일련의 규칙성을 찾을 수 있다.
1. dp값이 증가하는 경우는 찾으려는 알파벳이 동일한 경우를 찾는경우이다.
-> 사실 같은 알파벳을 만나야 부분배열의 길이를 증가시킬수 있으니 당연하다.
->왼쪽 대각선방향에 +1을 한 값임을 알 수 있다.
2. 동일하지 않은경우에는 이전기록들 중에서 가장 큰것을 가져간다.
-> dp상으로 자신의 위와 왼쪽의 것만 비교하면 된다.
이를 생각하고 dp를 채워나가는데 해당 문제에서는 알파벳 도 가져가야하므로 정답을 저장할 배열을 만든 후에 사용해주었다.
728x90
'Python > 백준' 카테고리의 다른 글
| 9019_DSLR (0) | 2022.04.27 |
|---|---|
| 13913_숨바꼭질 (0) | 2022.04.26 |
| 14003_ 가장 긴 증가하는 수열 (0) | 2022.04.23 |
| 14002_가장 긴 증가하는 수열 (0) | 2022.04.20 |
| 12582_1로 만들기 2 (0) | 2022.04.19 |