[dp/백준] 9251번: LCS

-문제: https://www.acmicpc.net/problem/9251

 

기억에 의존하긴 했지만, 스스로 푼 문제다 

주어진 단어 길이들로 2차원 행렬을 만든뒤, 완전 탐색으로 문자가 같은 경우와 아닌경우에 대한 점화식을 세우고 

코드로 점화식을 구현하면 된다.

 

점화식

LCS(x[i],y[j]) = LCS(x[i-1],y[j-1])+1 (if x[i]==y[j])

                       = max(LCS(x[i-1],y[j]),LCS(x[i],y[j-1])) (if x[i] != y[j])

 

 

초기화를 하는게 약간 어려웠는데, 0행과 0열을 기준으로 같은 문자인 경우만 1로 바꾸면 된다고 생각했는데 틀린 답은 출력했다. 원래는 4를 출력해야하는데 3을 출력함 

 

원인을 생각해보니 3행 0열에는 0이 아니라 1이 있어야 한다. 앞에 A로 같은 문자가 있는게 누적돼야하므로 

근데 이를 누적하지 않아서 4가 아닌 3이 출력된 것 같다. 

그래서 0행과 0열에 대해서 값 비교 및 누적을 먼저 한 후 나머지에 대해서 연산을 했더니 정답으로 떴다 

 

-정답풀이 

x=list(input())
y=list(input())
n=len(x)
m=len(y)
dp=[[0]*n for _ in range(m)]

if x[0]==y[0]:
    dp[0][0]=1
else:
    dp[0][0]=0
    
for i in range(1,n):
    if x[i]==y[0]:
        dp[0][i]=1
    else: 
        dp[0][i]=dp[0][i-1]
        
for j in range(1,m):
    if y[j]==x[0]:
        dp[j][0]=1
    else:
        dp[j][0]=dp[j-1][0]

for i in range(1,m):
    for j in range(1,n):
        if y[i]==x[j]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
            
print(dp[-1][-1])

 

-더 짧은 풀이 

import sys

s1=sys.stdin.readline().strip().upper()
s2=sys.stdin.readline().strip().upper()
len1=len(s1)
len2=len(s2)
dp=[[0 for i in range(len2+1)] for j in range(len1+1)]
#i==0, j==0일 때는 dp값 0 + 글자수니까 전체 행렬 길이= 글자길이+1

for i in range(1,len(s1)+1):
    for j in range(1,len(s2)+1):
        if s1[i-1]==s2[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
print(dp[-1][-1])