[백준 9251번] LCS (파이썬, 최장 공통 부분 수열, DP)
Posted by 해랑쓰 블로그 (Haerang's blog)
연속된 부분 수열은 아니고 각 문자열을 이루고 있는 문자들 순서만 맞춰서 최장 공통 부분 수열을 구하는 문제이다 a, b 두 문자열의 길이 +1 (각 첫번째 인덱스에 들어가는 값은 초기값인 0이다.) 인덱스 i,j를 비교해서 a와 b의 각 위치에 들어간 문자가 같다면 이전 최대 길이 +1 을 해주면 된다. 1: acaykp , 2: capcak에서 1의 부분 문자인 a(인덱스 0)만 봤을 때 2에서 c인 경우 0, ca인 경우 1 이런식으로 추가되는 문자가 같다면 1 증가시키는 식으로 해결한다. import sys input=sys.stdin.readline a=input().strip() # 엔터키도 들어가지 않도록 b=input().strip() # print(a,len(a)) dp=[[0]*(len..