[백준] 9249 최장 공통 부분 문자

문제

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

문제 풀이

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

• 아래와 같이 풀면 메모리 초과로 틀림.
• 메모리 줄일려고 생각해봤는데 아예 방법을 바꿔야할 것 같음.

시간복잡도, 공간복잡도

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

source