글 읽기 - 반례를 찾아주세요 ㅠㅠ

ajtwlstmdgks 4년 전 0

dp[i][j]의 정의는

s문자열 첫번째부터 i번째까지의 부분문자열을

t문자열 첫번째부터 j번째까지의 부분문자열로 의 최소편집 횟수입니다.

틀렸습니다 라고 나옵니다

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
int dp[1006][1006];

int main() {
	string s, t;

	cin >> s >> t;
	s = ' ' + s;
	t = ' ' + t;
	for (int i = 0; i <= s.length(); i++) {
		dp[i][0] = i;
	}

	for (int j = 0; j <= t.length(); j++) {
		dp[0][j] = j;
	}

	for (int i = 1; i <= s.length(); i++) {
		for (int j = 1; j <= t.length(); j++) {
			if (s[i] == t[j]) dp[i][j] = dp[i - 1][j - 1];
			else {
				dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
				if (s[i - 1] == t[j] && s[i] == t[j - 1]) 
					dp[i][j] = min(dp[i][j], dp[i - 2][j - 2] + 1);
			}
		}
	}
	int sol = dp[s.length()][t.length()];
	cout << sol;

}

작성하신 알고리즘은 OSA distance에 대한 코드로 보입니다. Wikipedia에 따르면, OSA 역시 Damerau-Levenshtein distance의 한 종류라고는 하지만, "no substring is edited more than once"라는 졔약이 있습니다 ㅠㅠ 이 문제는 OSA distance가 아닌 LD-distance with adjacent transposition을 요구하는 문제입니다. 그래서 위의 알고리즘이 WA가 나오는 것입니다.

자세한 내용은 Wikpedia에서 [Damerau-Levenshtein distance](https://en.wikipedia.org/wiki/...)를 읽어보시면 될 것 같습니다!!

반례는 예시 테스트 케이스에도 나오는 아래의 경우입니다!!

ca
abc
// 정답: 2
// 위의 코드: 3

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

문제

문제

출처

ICPC

반례를 찾아주세요 ㅠㅠ

ajtwlstmdgks 4년 전 0

bluehorn07 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말