LCS 9251

    
LCS 9251

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

 dp문제 였다.
그것도 모르고 set으로 풀다가 메모리 초과남.
이렇게 간편하게 될줄 알았는데..
오산이고
```python
tmp1=input()
tmp2=input()

subsets_tmp1=set([""])
for i in range(len(tmp1)):
    subsets_tmp1.update(list(map(lambda x: x+tmp1[i],subsets_tmp1)))
    
subsets_tmp2=set([""])
for i in range(len(tmp2)):
    subsets_tmp2.update(list(map(lambda x: x+tmp2[i],subsets_tmp2)))
subsets_inter=subsets_tmp1.intersection(subsets_tmp2)

print(len(max(subsets_inter,key=len)))

```

dp로 이렇게 풀어서 됬는데
이차원 배열로 비교하다가
같으면 그 대각선꺼 +1
다르면 위 왼쪽꺼 비교이다.
이런 식


```python
# 9251
str1=input()
str2=input()


dp=[[0 for i in range(len(str1))] for j in range(len(str2))]

samefound=False
for i in range(len(str1)):
    
    if str1[i]==str2[0]:
        samefound=True
    if samefound:
        dp[0][i]=1

samefound=False
for j in range(len(str2)):
    
    if str1[0]==str2[j]:
        samefound=True
    if samefound:
        dp[j][0]=1

        
for i in range(1,len(str1)):
    for j in range(1,len(str2)):
        if str1[i]==str2[j]:
            dp[j][i]=dp[j-1][i-1]+1
        if str1[i]!=str2[j]:
            dp[j][i]=max(dp[j-1][i],dp[j][i-1])
            
print(dp[-1][-1])

```