글 읽기 - 반례 좀 도와주세요ㅠㅠ

rktkek456 5년 전 0

CAPCAK
ACAYKP

이렇게 입력을 넣었을때 전형적인 LCS 길이 구하는 방법을 쓰면

정답인 4가 나오지만 LCS를 출력해보면 CAPK 이렇게 출력되는 문제가 있더라구요...

원래 K는 포함 되면 안되는데 포함되는 문제 때문에

가장 마지막 글자에서 길이가 증가하면 더 이상 루프를 진행하지 못하고 탈출하게 소스코드를 짰습니다.

그리고 배열(메모이제이션)에서 불러올때가 아니라 실제로 값이 1 증가 하는 부분에서 LCS문자열을 구했는데

반례가 뭐가 있을까요ㅠㅠ

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

typedef struct returnValues {
	int maxLength;
	string LCS;
}retrunValues;

returnValues findLCS(string stream1, string stream2) {
	returnValues ans;
	vector<vector<int>> cache = vector<vector<int>>(stream1.size() + 1, vector<int>(stream2.size() + 1, 0));
	string LCS = "";
	int maxLength = 0;
	bool escape = false;

	for (int i = 0; i <= stream1.size(); ++i) {
		if(escape == true)
			break;

		for (int j = 0; j <= stream2.size(); ++ j) {
			if (i == 0 || j == 0)
				cache[i][j] = 0;
			else if (stream1[i - 1] == stream2[j - 1]) {
				cache[i][j] = cache[i - 1][j - 1] + 1;
				maxLength = cache[i][j];
			}
			else {
				cache[i][j] = max(cache[i - 1][j], cache[i][j - 1]);
			}
		}
		if (cache[i][stream2.size()] - 1 == cache[i][stream2.size() - 1]) {
			escape = true;
			break;
		}
	}

	int counter = 0;
	for (int i = 1; i <= stream1.size(); ++i) {
		for (int j = 1; j <= stream2.size(); ++ j) {
			if (cache[i][j] == counter + 1 && cache[i - 1][j - 1] == cache[i - 1][j] 
				&& cache[i - 1][j - 1] == cache[i][j - 1]) {
				counter += 1;
				LCS += stream1[i - 1];
			}
		}
	}
	ans.maxLength = maxLength;
	ans.LCS = LCS;

	return ans;
}

int main() {
	string stream1, stream2;
	cin >> stream1 >> stream2;
	returnValues a = findLCS(stream1, stream2), b = findLCS(stream2, stream1);
	
	if(a.maxLength > b.maxLength)
		cout << a.maxLength << endl << a.LCS;
	else
		cout << b.maxLength << endl << b.LCS;
}

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

문제

문제

출처

ICPC

반례 좀 도와주세요ㅠㅠ

rktkek456 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말