문제

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

사용개념

LCS = Longest Common Sense

헷갈릴 수 있는 포인트

인덱스 처리하는데 주의해야한다.
열과 행을 처리하는 인덱스를 잘 줘야한다.

갱신하는 규칙 신경쓰기

    graph[i][j] = max(graph[i-1][j], graph[i][j-1])
    # 같은 경우 1을 더한다.
    if string1[j]==string2[i]:
        graph[i][j]=graph[i-1][j-1]+1

그래프 풀이

풀이 코드

import sys
input = sys.stdin.readline
string1 = '0'+input().rstrip()
string2 = '0'+input().rstrip()

n = len(string1)
m = len(string2)

graph = [[0]*n for _ in range(m)]

for i in range(1, m):
    for j in range(1,n):
        # 좌 또는 상의 값에서 최대값에 
        graph[i][j] = max(graph[i-1][j], graph[i][j-1])
        # 같은 경우 1을 더한다.
        if string1[j]==string2[i]:
            graph[i][j]=graph[i-1][j-1]+1
print(graph[m-1][n-1])