[알고리즘/DP] 9251번 : LCS - python

링크 : https://www.acmicpc.net/problem/9251

9251번: LCS

 

---

• 문제
• 소요시간: 1시간 실패

---

• 설계하기(접근방법) 

1. 입력받기

문자를 입력받는다

 

2. 구현하기

이 문제는 이중배열을 만들어서 두 문자를 비교한다

 

A와

CAPCAK

011111

 

AC와

CAPCAK

011222

 

ACA와

CAPCAK

011233 ....

 

이런 방식으로 이전 배열에서

새로운 같은 글자가 나타난 경우

+1을 해준다

 

이러한 방식으로 가장 긴 부분 문자열을 만든다

 

3. 출력하기

 

가장 긴 부분 문자열의 크기를 출력한다

 

---

• 코드(출력)

first = input()
second = input()


dp =[[0 for _ in range(len(second) + 1)] for _ in range(len(first) + 1) ]

for i in range(1, len(first) + 1):
    for j in range(1, len(second) + 1):
        if first[i-1] == second[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

print(dp[-1][-1])

---

• 얻어갈 부분

1. 이해하기 매우 어려웠던 문제다. 문자열을 어떻게 저렇게 비교하는지, 왜 저렇게 비교해야하는지 한참 걸렸다.