[알고리즘] 백준 9251 LCS

📖문제

9251 LCS

💡구상

문자열이 최대 1000글자로 이루어져 있으므로, 모든 경우의 수를 생각하려면 2^1000 이므로 DP를 사용하자.

그렇다면 DP 배열을 어떻게 만들어야 할까?
우선 예제를 바탕으로 살펴보자.

DP

위는 C와 "A", "AC", "ACA", ... "ACAYKP" 문자열을 비교했을때 LCS 값을 채워나간 것이다.
계속 채워보자.

끝까지 채워나가면 다음 2가지의 규칙을 얻을 수 있다.
1. 해당 칸의 행과 열의 문자가 같을 때는 해당 칸의 왼쪽 대각선의 값에 +1
2.** 해당 칸의 행과 열의 문자가 다를 경우 해당 칸의 왼쪽, 위의 값 중 큰 값을 가져온다.

점화식

이를 바탕으로 점화식으로 세우면
1. dp[i][j] = dp[i][j]+1
2. dp[i][j] = max(dp[i-1][j],dp[i][j-1])

🔍코드

#include<bits/stdc++.h> 
using namespace std;
string s1,s2;
int dp[1002][1002]; 
int main(){
	cin.tie(NULL); //입출력 묶음 해제
    ios_base::sync_with_stdio(false);
	cin>>s1>>s2;
	for(int i=1; i<=s1.size(); i++){
		for(int j=1; j<=s2.size(); j++){
			if(s1[i-1]==s2[j-1]) dp[i][j] = dp[i-1][j-1]+1;
			else dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
		}
	}
	cout<<dp[s1.size()][s2.size()];
}

🔥배운 점

DP문제에서 점화식을 찾아서 문제를 해결하는 방식이 가장 어려운것 같다😥

어려워 보이더라도 작은 경우부터 차근 차근 확장시켜 나가면서 전체의 규칙을 찾도록 노력해보자!