![[5582번] 공통 부분 문자열](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbkYFHE%2FbtqxF9ZuIOB%2Fl6i1vqKZZNkM5XzWsjvrJk%2Fimg.png)
5582번: 공통 부분 문자열
문제 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다. 두 문자열 ABRACADABRA와 ECADADABRBCR
www.acmicpc.net
LCS 알고리즘에 대해 아시나요?
혹시 모르신다면 [여기]를 참고하시고 다시 와 주세요.
아무튼 이 문제는 LCS 문제와는 약간의 차이가 있습니다.
그때는 각각의 문자들이 떨어져 있는 것도 허용이 됐지만, 이번에는 연결되어 있을 때에만 부분 문자열이라 할 수 있습니다. ( 연결되어 있는 문자열 - substring [v] / 연결되어 있지 않은 문자열 - subsequence )
이 점을 염두해 두고 풀어보도록 하죠.
LCS 문제와 같이 DP table을 만드는 것까지는 같습니다.
하지만 만들 때 값을 넣어주는 조건이 가장 중요하죠.
그 조건을 만들 때 중요한 건, 하나의 문자를 대조했을 때 같다면 이전 결과값을 가져와야 한다는 것입니다.
그러므로 이전 결과값만을 가져와서 거기에 +1만 한다면 연결되어 있는 조건을 만족시키며 최대 길이를 찾을 수 있을 것입니다.
저는 처음에 저 조건 자체는 쉽게 생각할 수 있었습니다.
하지만 자꾸 이상한 결괏값이 나와서 뭐지하고 생각하다가 "같을 때에만" 이전 결과값을 가져와야 한다는 것을 놓치고 있다는 것을 알았습니다.
이를 만족시켜주는 if 값을 넣어주지 않으니 같지 않은 문자임에도 불구하고 값이 계속 질질 끌리더라구요.
이 문제를 통해 조건을 정확히 설정해주어야 한다는 것을 깨달았습니다.