LCS1 [백준/C++] #9251 LCS (DP/LCS) 문제https://www.acmicpc.net/problem/9251 구상사실.. 문제 이름 자체가 LCS여서... 바로 LCS 대입해서 풀었다. 알고리즘: LCS (Longest Common Subsequence) 두 수열이나 문자열에서 공통되는 가장 긴 부분수열 혹인 부분 문자열 중요한건, 공통되는 문자열이 연속적일 필요는 없다! LCS는 2차원 DP 배열을 통해 구할 수 있다. 풀이 + 코드if (현재 비교하는 문자가 서로 다르다면) 왼쪽, 위쪽 두 개의 값 중 큰 값 저장else 왼쪽 위 대각선의 값 + 1 저장 #include #include using namespace std;string s1, s2;vector> dp;/*9251 LCS*/int main() { cin >> s1 >> .. 2024. 7. 5. 이전 1 다음
