백준 9251 LCS(c++)

https://www.acmicpc.net/problem/9251

9251번: LCS

<코드>

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	vector<vector<int>>v(1001,vector<int>(1001,0));
	string s1,s2;
	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]){
					v[i][j] = v[i-1][j-1]+1;
				}
				else{
					v[i][j] = max(v[i-1][j],v[i][j-1]);
				}
			}
		}
	cout<<v[s1.size()][s2.size()];
}

<풀이 과정>

이 문제는 동적 계획법으로 풀 수 있다.

우선적으로 문자열의 최대 길이가 1000이므로 크기가 1001인 2차원 벡터를 선언함과 더불어 값을 0으로 초기화해준다.

이제 문자가 같은 부분이 나오면 v[i][j]=v[i-1]v[j-1]+1 식처럼 값을 1씩 더해주면 되고,

만약에 다르다면, 바로 앞부분과 윗부분을 비교해줘서 큰 것을 삽입하면 된다.

ex) ABCD, BCDF

 

 

	A	B	C	D
B	0	1	1	1
C	0	1	2	2
D	0	1	2	3
F	0	1	2	3

 

      

다음과 같이 작성할 수 있는데 같은 값이 나오는 부분은 +1 해주었고, 값이 다르다면 윗부분과 앞부분의 값을 비교해 큰 것을 대입시켜준다. 동적 계획법을 쓰면 좋은 이유가 앞의 원소의 값을 다음 원소의 값을 구하기 위해 사용하기 때문에 더욱 시간효율을 극대화할 수 있다는 장점이 있다.