[Python Algorithm] 공통 부분 문자열 BOJ #5582

문제

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

5582번: 공통 부분 문자열

 

내 문제 풀이

import sys

a = sys.stdin.readline().strip()
b = sys.stdin.readline().strip()
cnt = [[0 for _ in range(len(b) + 1)] for _ in range(len(a) + 1)]

for i in range(len(a)):
    for j in range(len(b)):
        if a[i] == b[j]:
            cnt[i+1][j+1] = cnt[i][j] + 1

print(max(map(max, cnt)))

👉 DP, 문자열 문제

2차원 배열을 만들고, 대각선으로 연속되는 문자열을 카운트해서 누적해주면 된다.

 

💡 피드백

시간초과, 메모리 초과를 주의해서 풀어야 한다.

근데 난 아무리 풀어도 한계가 있어서 결국 pypy로 제출했다.ㅜ

다음에 다시 한 번 풀어봐야겠다,,