[BOJ] 9251. LCS

www.acmicpc.net/problem/9251

9251번: LCS

문제 : 최장 공통 부분 수열을 찾아라.

⊙ DP - 다이나믹 프로그래밍

 

제가 백준에서 코드 1등을 했습니다!!

감격쓰~~ ㅎㅎㅎ

 

감격을 뒤로 하고!

풀이 방법은 DP를 설정하고, DP에 한 배열에서 최장 공통 수열이 되는 대로 찾는 겁니다.

첫 번째 배열의 인덱스 처음부터 끝까지 하나씩을 순서대로 골라, 두 번째 배열 전체를 탐색하면서

둘이 같은지를 비교합니다. 그러면 딱 맞는 수가 나오고 그 수에서 max_dp를 하나 더해주면 됩니다.

 

이게 가능한 이유는 DP 배열의 인덱스는 두번째 배열의 인덱스와 같게 설정되어 저장되고,

그 전의 max_dp는 이미 저장되어 있는 dp를 기준으로 설정하기 때문입니다.

 

그리고 코드를 잘 못 보다보면 '배열안에 똑같은 값이 두개 있으면 어떻게 되냐?'

라고 생각할 수도 있는데, 그 부분은 두 번째 배열이 돌아가면서 max_dp의 값은

예전 dp의 최댓값보다 절대 높게 설정이 될 수 없으므로 문제가 해결됩니다.

 

한 번 보시고 각자의 코드를 찾아보시기 바랍니다 ㅎㅎ

 

코드:

def s():
    s1, s2 = input(), input()
    dp = [0] * 1000
    for i in range(len(s1)):
        max_dp = 0
        for j in range(len(s2)):
            if max_dp < dp[j]:
                max_dp = dp[j]
            elif s1[i] == s2[j]:
                dp[j] = max_dp + 1
    print(max(dp))
s()