[백준]9251 LCS

yylog·2022년 9월 18일
0
post-custom-banner

문제

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

소스코드

import sys
input = sys.stdin.readline


if __name__ == "__main__":  
    a = '0' + input().rstrip() #마진 주기
    b = '0' +input().rstrip() #마진 주기

    #각 문자열의 길이 찾기
    len_a = len(a) 
    len_b = len(b) 

    #dp 저장소
    lcs = [[0] * (len_b) for _ in range(len_a)]

    #lcs 길이 탐구
    for i in range(1,len_a):
        for j in range(1,len_b):     
            if a[i] == b[j]:#문자가 같은 경우, 바로 위 대각선 lcs 값에 + 1
                lcs[i][j] = lcs[i-1][j-1] + 1
            else: #같지 않은 경우 위쪽의 최댓값과 왼쪽의 최댓값중 큰 값
                lcs[i][j] = max(lcs[i-1][j],lcs[i][j-1])
    
    print(lcs[len_a-1][len_b-1]) #이 문제의 답
    
    #LCS 찾기 -- 이건 문제는 아닌데 공부용
    res = ""
    i = len_a-1
    b = len_b-1
    
    while 1:
        if lcs[i][j] == 0:
            break #lcs 값이 0 이 나오면 종료 더이상 없다는거
        #위나 왼쪽과 같은 값이 있다 -> 같지 않은 값
        if lcs[i][j] == lcs[i-1][j]:
            i = i-1 
        elif lcs[i][j] == lcs[i][j-1]:
            j = j-1
        #위나 왼쪽에 같은 값이 없다?대각선 위로 올라가고 그 값이 공통 값이므로 추가해주기
        else:
            res += a[i]
            i = i-1
            j = j-1
    print(res[::-1])

설명

2가지 경우의 수로 나누어서 점화식을 세워볼 수 있다.

1. 마지막 문자가 같은 경우

마지막 문자를 제외한 나머지 문자열의 갯수를 구하면 된다.
LCS[i][j] = LCS[i-1][j-1] + 1

2. 마지막 문자가 같지 않은 경우

주어진 첫번째 문자열에서 문자를 제외한 경우와 두번째 문자열에서 문자를 제외한 경우 중 큰 값을 구한다.
LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])

LCS 2차원 배열을 생성하여 Bottom-Top 방식으로 위의 점화식을 계산하여 배열을 채워넣은 후 가장 max 값 LCS[첫번째 배열의 문자열 길이][두번째 배열의 문자열 길이] 가 최종 정답이 된다.

후기

[[0] * lenb for _ in range(lena)] 이렇게 세팅을 해놓고 아래 이중 For문을 돌릴 때 행과 열 잘못 설정해서 index error 남;;; 잘 체크하자

공부할 때 사용한 참고자료

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence

profile
경험하고 공부한 모든 것을 기록하는 공간
post-custom-banner

0개의 댓글