[C++] 백준 9251. LCS

🌽 문제

🥕 입출력

🥔 풀이

2중 for문으로 두 문자열을 각각 돌며 dp를 갱신한다.
문자가 서로 같을 땐 두 문자 모두에 도달하기 전까지 dp 값에 1을 더해주고,
다를 땐 각각의 문자에 도달하기 전까지 dp 값을 비교하여 더 큰 넘으로 갈아낀다.

🥬 코드

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

int dp[1001][1001];

int main() {
	string a, b;
	cin >> a >> b;

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

	return 0;
}

🥜 채점

ios어쩌구는 안먹혔다