알고리즘/백준
[백준] 9251번(python 파이썬)
G_Gi
2021. 2. 26. 17:22
SMALL
처음에 무작위로 뽑았을때 만들수 있는 집합중 공통된 가장 긴 것을 찾는줄 알았다..
풀이
만약 s1[i] == s2[j]라면 ( 추가한 문자가 같을때 )
dp[i][j] = dp[i - 1][j - 1] + 1 ( 추가되기전 값 + 1)
다르면
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) (추가되기 전 값들 중 가장 큰 값)
dp[i]j] | C | A | P | C | A | K | |
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 |
s1 = ' '+input()
s2 = ' '+input()
dp = [[0] * len(s2) for _ in range(len(s1))]
for i in range(1, len(s1)):
for j in range(1, len(s2)):
if s1[i] == s2[j]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
print(max(max(dp)))
LIST