[백준] 5582 공통 부분 문자열

문제

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

문제 풀이

1. 마지막 끝자리를 확인한다.
2. 마지막 끝자리가 같으면 각각의 문자열의 이전 문자가 같은지 확인한다.
3. 위에 1,2 번을 반복한다.
4. 반복하면서 동적 계획법을 사용하여 caching 을 한다.

시간복잡도, 공간복잡도

• 시간복잡도 : O(n제곱) - for 2번 돌아감.
• 공간복잡도 : O(n제곱) - caching 이 2차원배열이기에

source