< 백준 BaekJoon : 9251번 LCS > C++

<< 문제 >>

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

9251번: LCS

 

LCS는 대표적인 DP 문제입니다.

 

저는 그걸 모르고 새롭게 풀어보려고 고생을 했었네요.

 

 

 

<< 코드 >>

 

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

int dp[1001][1001];

int main() {

	string str1, str2;
	cin >> str1 >> str2;

	for (int i = 1; i < str1.length()+1; i++) {
		for (int j = 1; j < str2.length()+1; j++) {
			
			if (str1[i-1] == str2[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[str1.size()][str2.size()];
}

 

 

 

 

<< 깃헙 >>

 

 

https://github.com/J2on/StudyAlgorithm_Part2/tree/main/%EB%B0%B1%EC%A4%80/Gold/9251.%E2%80%85LCS