[G5] 백준 9251번 LCS C++ 다이나믹 프로그래밍

리뷰

 

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

문자열 두개 중 최장 공통 부분 수열의 길이를 구하는 문제

 

전역 변수

• dp : 문자열 a, b의 LCS를 동적계획법으로 찾으며 각 단계를 저장할 2차원 정수 배열 크기는 1001 * 1001로 초기화

 

함수

없음

 

 

문제풀이

1. 문자열 두개를 각각 문자열 변수 a, b에 저장한다.
2. a, b의 길이를 각각 정수형 변수 len1, len2에 저장한다.
3. len1 * len2 크기의 2중 for문을 개행해 준다. 이때 인덱스는 1부터 문자열의 길이까지 포함되도록 한다.
4. a, b의 현재 탐색범위 이전의 문자가 같을 경우 현재 dp인덱스를 이전 dp인덱스 + 1로 저장해 준다.
5. 같지 않을 경우 i의 현재 인덱스, j의 이전 인덱스값과 i의 이전 인덱스, j의 현재 인덱스 값을 비교한다.
6. 더 큰 값을 dp의 현재 인덱스로 저장해 준다,
7. 탐색을 마친 후 dp배열의 len1, len2 인덱스에 저장된 값을 출력해 준다.

 

참고 사항

점화식

if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);

 

 

정답 코드

#include<iostream>

using namespace std;

int dp[1001][1001];

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

	string a, b;
	cin >> a >> b;

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