[BAEKJOON] 5589 공통 부분 문자열

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; int main() { string input1, input2; cin >> input1 >> input2; int size1 = input1.size(), size2 = input2.size(); vector<vector<int>>DP(4001, vector<int>(4001, 0)); int answer = 0; for (int index1 = 0; index1 < size1; index1++) { for (int index2 = 0; index2 < size2; index2++) { if (input1[index1] == input2[index2]) { if (index1 == 0 || index2 == 0) DP[index1][index2] = 1; else DP[index1][index2] = DP[index1 - 1][index2 - 1] + 1; answer = max(answer, DP[index1][index2]); } } } printf("%d", answer); return 0; }

문제를 풀수록 느끼는 것이 있는데

알고리즘을 푸는 창의적인 방법을 생각해 내는 머리도 필요하지만

문제를 보고 유형을 알아내는 것도 중요한 것 같다

요새 문제가 잘 안풀리는 데 그건 내 창의력은 떨어지고

많은 문제유형을 풀어보지 않았기 때문에 새로운 문제 유형에 적응하는 일이라고 생각한다

2차 배열을 만들어서 같은 문자열이 있는지 살펴본다

문자열이 있으면 그 이전에 같았던 수 보다 1이 많은 것이기 때문에 DP[index1-1][index2-1]에 1을 더해주는 것이다.

활용도가 높을 것 같은 문제이다.