BOJ - 9252번 LCS 2(C++)

문제 출처 : https://www.acmicpc.net/problem/9252

문제 난이도

Gold 5

문제 접근법

최장 공통 부분 수열 알고리즘으로 알아두면 알고리즘이다.
이 문제를 처음 본 사람들은 LCS를 먼저 풀어보는 걸 추천한다.

LCS 처음 봤을 때 다른 블로그들을 아무리 참고해도 이해가 되지 않아 영상을 봤는데 이해가 확실히 잘 됐다.

https://youtu.be/EAXDUxVYquY

통과 코드

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


using namespace std;

int dp[1001][1001];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	string str1, str2, res="";
	cin >> str1 >> str2;
	int N = str1.size();
	int N2 = str2.size();
	for (int i = 0, j = 0; i <= N, j <= N2; i++, j++) {
		dp[i][0] = 0;
		dp[0][j] = 0;
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N2; j++) {
			if (str1[i - 1] == str2[j - 1]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}
	while (N > 0 && N2 > 0) {
		if (dp[N][N2] == dp[N - 1][N2]) {
			N--;
		}
		else if (dp[N][N2] == dp[N][N2 - 1]) {
			N2--;
		}
		else {
			res = str1[N - 1] + res;
			N--;
			N2--;
		}
	}
	cout << dp[str1.size()][str2.size()] << "\n";
	if (dp[str1.size()][str2.size()] > 0) cout << res << "\n";
	return 0;
}

피드백

처음에는 dp 점화식 대로하고 문자가 같을 때, res에 넣었다. 중복을 피하려고 check bool 배열을 뒀다.

for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N2; j++) {
			if (str1[i - 1] == str2[j - 1]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
				if (!ch[dp[i][j]]) {
					res += str1[i - 1];
					ch[dp[i][j]] = true;
				}
			}
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}

하지만 이 생각은 잘못됐다. 같은 숫자를 체크해서 중복을 체크하는 것이 아니라-이러면 제대로 된 부분 순열이 나오지않는다- 대각선 일 때 +1 한 거처럼 점화식과 비슷하게 생각하는 것이였다.