백준 9251 - LCS

123456789101112seq1 = input()seq2 = input()dp = [[0]*(len(seq2)+1) for _ in range(len(seq1)+1)] for i in range(1,len(seq1)+1): for j in range(1,len(seq2)+1): if seq1[i-1] == seq2[j-1]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i][j-1], dp[i-1][j]) print(dp[-1][-1])Colored by Color Scriptercs 입력: ACAYKP CAPCAK 0 C A P C A K 0 0 0 0 0 0 0 0 A 0 0 1 1 1 1 1 C 0 1 1 1 2 2 2 A 0 1 2 2 2 3 3 Y 0 1 2 2 2 3 3 K 0 1 2 2 2 3 4 P 0 1 2 3 3 3 4 공백의 표를 만들고 seq1[i] 와 seq2[j]에 같은 값이 있다면 이전 dp값에 1을 더하고값이 다르다면 dp[:j] 와 dp[:i] 범위의 dp에서 큰 값을 dp[i][j]에 넣는다. ..........

원문링크 : 백준 9251 - LCS