문제 링크입니다: https://www.acmicpc.net/problem/9252
백준 9251번인 LCS(http://jaimemin.tistory.com/370?category=988050)를 풀었다면 쉽게 풀 수 있는 문제였습니다.
인덱스를 하나씩 증가하며 공통부분을 찾아내는 식으로 프로그램을 작성했습니다.
/*
LCS(Longest Common Subsequence, 최장 공통 부분 순열) 문제는
두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장
긴 것을 찾는 문제이다.
LCS의 길이와 공통부분을 구하시오
*/
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring> //memset
using namespace std;
int cache[1000][1000]; //최대 길이 1000
string s1, s2;
string result;
int LCS(int idx1, int idx2) //s1과 s2의 인덱스를 전달받음
{
//기저 사례: 문자열의 범위 벗어날 경우
if (idx1 == s1.size() || idx2 == s2.size())
return 0;
int &result = cache[idx1][idx2];
if (result != -1)
return result;
//총 3가지의 경우의 수를 고려
//1. s1만 인덱스 증가했을 경우
//2. s2만 인덱스 증가했을 경우
//3. s1과 s2 모두 인덱스 증가했을 경우
return result = max(LCS(idx1 + 1, idx2), max(LCS(idx1, idx2 + 1), LCS(idx1 + 1, idx2 + 1) + (s1[idx1] == s2[idx2])));
}
void reconstruct(int idx1, int idx2)
{
//기저 사례(인덱스 범위 초과시 그만)
if (idx1 == s1.size() || idx2 == s2.size())
return;
//공통부분 찾았을 경우
if (s1[idx1] == s2[idx2])
{
result += s1[idx1];
reconstruct(idx1 + 1, idx2 + 1);
}
//s1의 인덱스를 추가했을 경우 s2의 인덱스를 추가했을 때보다 LCS의 길이가 크거나 같은 경우
else if (cache[idx1 + 1][idx2] >= cache[idx1][idx2 + 1])
reconstruct(idx1 + 1, idx2);
else
reconstruct(idx1, idx2 + 1);
}
int main(void)
{
cin >> s1 >> s2;
memset(cache, -1, sizeof(cache));
cout << LCS(0, 0) << endl;
reconstruct(0, 0);
cout << result << endl;
return 0;
}
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
백준 2193번 이친수 (0) | 2018.02.12 |
---|---|
백준 9095번 1, 2, 3 더하기 (0) | 2018.02.11 |
백준 9461번 파도반 수열 (0) | 2018.02.09 |
백준 1912번 연속합 (0) | 2018.02.07 |
백준 2965번 캥거루 세마리 (0) | 2018.02.07 |