[Baekjoon] 9251번: LCS

🥅 문제

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

 

🔍 설계

초기에는 일차원 배열을 선언하고, strA와 strB를 이중 반복문으로 순회하면서, 같으면 그 인덱스까지의 최장 거리를 증가시키는 방식으로 시도했지만, 순서가 고려되지 않는 문제가 발생한다.

 

따라서, 이차원 배열로 선언하여, dp[i][j]는 strA에서 i번째, strB에서 j번째까지 최장 길이를 저장한다.

 

dp[0][0]을 초깃값으로 이용하기 위해, 반복문을 1부터 문자열의 길이까지 반복한다. 문자열은 0부터 시작하므로, 문자열에서는 i-1, j-1을 이용한다.

 

strA[i-1]과 strB[j-1]이 같으면, dp[i][j]를 dp[i-1][j-1]+1로 갱신한다. 두 문자열에서 각각 i와 j가 되기 전의 최장 길이에 1을 더하는 것이다.

 

strA[i-1]과 strB[j-1]이 다르면, dp[i][j]를 dp[i-1][j]와 dp[i][j-1] 중 큰 값으로 갱신한다. dp[i-1][j]와 dp[i][j-1]는 dp[i][j]가 아닌 것 중에 최장 길이가 저장되어 있다.

 

👊 풀이

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

int dp[1001][1001];
string strA, strB;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> strA >> strB;

	for (int i = 1; i <= strA.length(); i++) {
		for (int j = 1; j <= strB.length(); j++) {
			if (strA[i-1] == strB[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[strA.length()][strB.length()] << "\n";
	return 0;
}