Baekjoon 5582.py [공통 부분 문자열]

hohooodo·2021년 7월 22일
0

Problem Solving

목록 보기
28/32
post-thumbnail

문제가 궁금하다면?

import sys
input = sys.stdin.readline
w1 = input().rstrip()
w2 = input().rstrip()

dp = [[0]*(len(w2)+1) for _ in range(len(w1)+1)]
result = 0

for i in range(1, len(w1)+1):
    for j in range(1, len(w2)+1):
        if w1[i-1] == w2[j-1]:
            dp[i][j] = dp[i-1][j-1]+1
            result = max(result, dp[i][j])
print(result)

풀이 복기

하나씩 순회하면서 같은지 다른지 확인하면 당연히 시간초과 나서 다른방법으로 풀어야한다.
DP를 활용해 작성했는데 중요한부분은 아래 로직이다.
if w1[i-1] == w2[j-1]: dp[i][j] = dp[i-1][j-1]+1
현재 문자가 같다면, 이전 문자 상태 +1 해주는 방법으로 풀었다.

profile
글을 잘쓰는 개발자가 되고싶습니다

0개의 댓글