8. 백준 9252, DP - LCS(Longest Common Subsequence)

 

안녕하세요 공상 개발입니다. 

오늘은 LCS(Longest Common Subsequence) 유형의 백준 문제를 한번 풀어봅시다.

 

 

https://www.acmicpc.net/problem/9252

9252번: LCS 2

 

---

 

# 문제 LCS(Longest Common Subsequence, 최장 공통부분 수열) 문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. # 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. # 출력 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다. LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

 

# 예제 입력  ACAYKP CAPCAK

# 예제 출력 4 ACAK

 

---

# 관계식

 

# 로직

 X=<ACAYKP>, Y=<CAPCAK>  LCS의 길이 = C_6,6 = 4인 문제를 먼저 풀려면 테이블을 작성해야 됩니다.

 

연 파란색 부분과 파란색 부분은 traceback(되찾기)한 부분입니다.

테이블 작성 규칙은 위의 LCS 관계식에 맞춰 작성하면 됩니다.

처음 테이블 작성 시, 접근이 어려울 수 있지만 동일 예제 3번 정도 그려보면 어느 정도 감이 생깁니다.

 

---

# 소스 코드

 

---

 

 

작성된 내용 중 잘못된 정보나 접근이 있을 시, www.instagram.com/hong_.98/을 통해 말씀해 주시기 바랍니다.

좋은 하루 보내세요.