글 읽기 - LCS 역추적 코드 한번만 봐주시면 감사하겠습니다(주석있음!)

devbelly 4년 전 0

게시판에 반례도 다 돌려봤는데 잘 모르겠습니다.

제가 주석 적으면서도 헷갈려서 이해가 안되시는 부분있으면 꼭 지적 바랍니다.

어느부분이 틀린지 잘 모르겠습니다.

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


string A;
string B;
string C;
int DP[1002][1002];
int LCS(int a, int b) {

	if (a < 0||b<0) // 인덱스가 0 미만, 즉 존재하지 않는 인덱스에 접근 하면
		return 0; // 두 문자열 비교 종료. 길이는 0
	
	int& ret = DP[a][b];
	if (ret != -1) return ret;

	if (A[a] == B[b]) // 입력받은 인덱스에 대하여 두 문자가 같다면
		return ret = LCS(a - 1, b - 1) + 1; // 각 문자열에서 맨 뒤에 문자를 하나씩 빼고 LCS 호출. + 1은 뺸 문자를 세는 행동
	else 
		return ret = max(LCS(a - 1, b), LCS(a, b - 1)); // 두 문자가 다르다면  1)A[a]가 LCS에 포함될때, 2)A[a]가 LCS에 포함 안될때
														// 로 나눌수 있다. 1)경우라면 LCS(a-1,b) 2)경우라면 LCS(a,b-1)
}

void recon(int a, int b) { // 문자열 다시 만들기
	if (a <0 ||b <0) // 존재하지 않은 인덱스 접근하면 종료
		return;
	if (A[a] == B[b]) { // 같다면 
		C += A[a]; // 문자열에 A[a] 추가.
		recon(a -1, b -1); // DP[a-1][b-1]로 가자 . 올바르게 a번쨰,b번쨰 인덱스를 제거
	}
	else if(DP[a - 1][b] >= DP[a][b - 1]) // DP[a][b]는 A는 a인덱스까지 B는 b인덱스까지 고려했을때 만들수 있는 길이
		recon(a - 1, b);				// DP[a-1][b] 는 A문자열에서 a번쨰 인덱스를 고려 안하겠다는 뜻
	else								// a인덱스를 고려안해도 B문자열에서 b인덱스를 뺀것보다 크다면.
		recon(a, b - 1);				// 우리는 쓸데없는 a인덱스를 잘 제거한것이다. 
}

int main(){
	memset(DP, -1, sizeof(DP));
	cin >> A >> B; // 문자열 A,B 입력받는다 A: ACAYKP B: CAPCAK
	cout << LCS(A.size() - 1, B.size() - 1) << endl; // 해당 함수로 고고씽
	recon(A.size() - 1, B.size() - 1);
	 reverse(C.begin(),C.end());
	 cout << C;
	return 0;
}

djm03178 4년 전 1

recon 함수에서 a나 b가 0이면 34번째 줄에서 음수 인덱스에 접근하게 됩니다.

devbelly 4년 전 0

항상 감사드려요 ^^

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

LCS 역추적 코드 한번만 봐주시면 감사하겠습니다(주석있음!)

devbelly 4년 전 0

djm03178 4년 전 1

devbelly 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말