[9251] LCS(C++)

1. 문제

 

2. 접근 방법

- 못풀어서 해답을 찾아보았다.

http://melonicedlatte.com/algorithm/2018/03/15/181550.html

[백준] 9251번 C/C++ 풀이 _ LCS - Easy is Perfect

-  dp[i][j] : s1.substr(0,i) , s2.substr(0,j)의 LCS 길이 (i번째, j 번째 문자열을 선택했을 때가 아님)

   s1[i] == s2[j]이면, dp[i][j] = dp[i-1][j-1] + 1 (이전까지의 최장 길이 + 1, LCS가 갱신됨) 

   s1[i] != s2[j]이면, dp[i-1][j] 와 dp[i][j-1] 중 큰 값 (LCS자체는 갱신이 안됨. 표를 채우기 위한 과정)

 

 

3. 실수 한 것 & 깨달은 점

- 나는 해답을 볼 때 "내가 풀었던 방식이랑 해답이랑 어떤 차이가 있는지"를 찾는데 오래걸린다. 중요한 경우인데 문제는 너무.. 많이,, 걸린다는 것이다. 특히 아예 첫 단추부터 다르게 접근했을 때 오래걸린다. 당분간은 "해답을 이해하는데" 집중하고 어느 정도 실력이 향상되면 그 때 "해답과의 차이"에 집중해야 시간을 절약할 수 있을 것 같다..

 

-그리디와 dp의 차이를 아직 헷갈려한다. 그나마 다행인건 문제를 접근할 때 "앗 이거 그리디인데" 라는 느낌은 이제 어느정도 온다. 하지만 깨닫기만 하고 dp로 푸는 방법으로 가지는 못한다  좀 더 많이 풀어보자.

 

4. 코드 

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;


void solution(string s1, string s2) {

	if(s1.length() > s2.length()) swap(s1,s2);
	int dp[1001][1001] = {0,};

	for(int i=1;i<=s1.length();i++) {
		for(int j=1;j<=s2.length();j++) {
			if(s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1]+1;
			else dp[i][j] = max( dp[i-1][j],dp[i][j-1]);
		}
	}

	cout << dp[s1.length()][s2.length()];

}

int main() {
	ios_base::sync_with_stdio(NULL);
	cin.tie(0);

	string s1,s2;
	cin >> s1 >> s2;

	solution(s1,s2);
	return 0;
}