백준 9252번 LCS 2

< 백준 9252번 LCS 2 - 마포 코딩박 >

사용한 알고리즘: DP


 두 문자열 A, B 가 주어졌을 때, 최장 공통 부분 수열(LCS) 를 구하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 6~7)
 'dp[x][y] : 문자열 A의 0~x-1 까지, B의 0~y-1 까지 썼을 때, A의 남은 x~끝까지 와 B의 남은 y~끝까지로 만들 수 있는 LCS 길이' 로 설정하였습니다.

(2) (코드 17~30)
 dp[x][y] = max( dp[x][y+1], dp[x+1][y], dp[x+1][y+1]+ 1(A[x]=B[y]일때)or 0(A[x]!=B[y]일때)) 입니다. 이를 생각하여 dp값을 구하는 함수를 만들어주었습니다.

(3) (코드 17~30)
 만들어 놓은 dp 값을 추적하며 답을 구해주었습니다.

	#include <bits/stdc++.h>
	using namespace std;
	string A, B;
	string answer;
	// dp[a][b] : 첫 문자열의 a 번째 이후, 두번째 문자열의 b번째 이후로 만들 수 있는 LCS 길이
	int dp[1001][1001];
	int LCS(int idx1, int idx2){
	if(idx1==A.size() || idx2 == B.size()) return 0;
	int &result = dp[idx1][idx2];
	// 중복 방지
	if(result != -1) return result;
	return result = max(LCS(idx1,idx2+1),max(LCS(idx1+1,idx2),LCS(idx1+1,idx2+1)+(A[idx1]==B[idx2])));
	}
	void reconstruct(int idx1, int idx2){
	// 끝까지 왔으면 return
	if(idx1 == A.size() || idx2 == B.size()) return;
	// 해당 index 에서 첫 문자열 = 두번째 문자열 이면 정답에 추가
	if(A[idx1]==B[idx2]){
	answer += A[idx1];
	reconstruct(idx1+1,idx2+1);
	}
	// dp 값 큰 쪽으로 선택
	else if(dp[idx1+1][idx2]>=dp[idx1][idx2+1])
	reconstruct(idx1+1,idx2);
	else
	reconstruct(idx1,idx2+1);
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> A >> B;
	memset(dp,-1,sizeof(dp));
	cout << LCS(0,0) << '\n';
	reconstruct(0,0);
	cout << answer << '\n';
	return 0;
	}

view raw BOJ 9252.cpp hosted with ❤ by GitHub