[BOJ] 9251번 LCS

다음과 같이 2차원 배열 dp를 선언한 후 이중 for문으로 접근하면 되는 문제이다.

dp[i][j] : s1의 i번째, s2의 j번째까지의 최대 LCS 길이

이때, dp[i-1][j-1]과 같은 접근을 깔끔하게 처리하기 위해 맨 앞쪽 index를 dummy로 사용하여 모두 0으로 초기화 해서 사용했다.

s1 = input()
s2 = input()
s1 = " " + s1 # index를 1 ~ len(s1)-1로 참조하기 위해
s2 = " " + s2

# dp[i][j] : s1의 i번째, s2의 j번째까지의 최대 LCS 길이
dp = [[0 for _ in range(len(s2))] for _ in range(len(s1))] # 0으로 초기화

for i in range(1,len(s1)):
  for j in range(1,len(s2)):
    if s1[i] == s2[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[len(s1)-1][len(s2)-1])