글 읽기 - C++ 알고리즘 질문있습니다.

ryanmans 2년 전 0

검색을 통해 문제를 푸는 방법은 알았는데 제가 풀 던 방식이 왜 틀렸는지 모르겠어서 질문 드립니다.

저는 두 번째 문자열을 쪼개지 않고 첫 번째 문자열을 하나 씩 늘려가면서 해당 문자를 포함하는 LCS값을 dp[i][0]에 저장하고 그때 해당 문자의 두 번째 문자열 에서의 위치를 dp[i][1]에 저장했습니다.

알고리즘에 문제가 있다는 건 알겠는데 어디인지를 모르겠습니다..

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int arr1[1001]{ 0, };
int arr2[1001]{ 0, };
int n, m;
int Max = 0;
int dp[1001][2]{ 0, }; /* dp[i][0] 는 i 번째 문자까지의 LCS, dp[i][1]은 그때 문자의 두 번째 문자열에서의 위치 */
void ques(int k) {
	for (int i = 0; i < n; i++) {
		int p = find(arr2, arr2 + m, arr1[i]) - arr2; /* 첫 문자열의 문자가 두 번째 문자열에 있는지 확인 */
		if (p != m) {
			dp[i][0] = 1;
			dp[i][1] = p;
			for (int j = 0; j < i; j++) {/* 이전 문자들의 LCS값과 비교 */
				int q = find(arr2 + dp[j][1] + 1, arr2 + m, arr1[i]) - arr2; /* 문자가 LCS에 포함 될 수 있는지 확인 */
				if (q != m && dp[i][0] <= (dp[j][0] + 1)) {
					dp[i][0] = dp[j][0] + 1;
					dp[i][1] = q;
				}
			}
		}
		Max = max(Max, dp[i][0]);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	string a, b;
	cin >> a >> b;
	n = a.size();
	m = b.size();
	for (int i = 0; i < n; i++) {
		arr1[i] = a[i];
	}
	for (int i = 0; i < m; i++) {
		arr2[i] = b[i];
	}
	ques(0);
	cout << Max;
}

powergee 2년 전 1

반례 드립니다. 현재 알고리즘은 최적의 해를 찾지 못하고 있습니다.

아래 입력의 정답은 "ABB"를 선택하는 것으로 3이지만 ryanmans 님의 코드는 2를 출력하고 있습니다.

BABB
ABBA

ryanmans 2년 전 1

감사합니다!! 같은 문자가 나올 때 저장되는 위치가 다른 부분이 있었네요..

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

문제

문제

출처

ICPC

C++ 알고리즘 질문있습니다.

ryanmans 2년 전 0

powergee 2년 전 1

ryanmans 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말