글 읽기 - dp로 풀었는데 어디서 틀렸을까요?

hssk1528 4년 전 0

두 문자열의 인덱스를 하나씩 늘려가면서 삽입 문자열의 최소 개수를 구했습니다.

반례라도 알려주시면 정말 감사하겠습니다ㅜㅜ

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

using namespace std;

string O, N;  // 입력 문자열
int cache[1001][1001]; 

const int INF = 987654321;

int stringDist(int a, int b, bool prev) {
	// base case : 문자열 O가 끝났으면 뒤에 붙일 문자열 존재 여부에 따라 값 리턴
	if (a >= O.size()) {
		if (b >= N.size()) return 0;
		return 1;
	}

	// base case : 문자열 N이 끝났으면 O를 N으로 만들 수 없기 때문에 INF 리턴
	if (b >= N.size()) return INF;

	// 메모이제이션
	int& ret = cache[a][b];
	if (ret != -1) return ret;

	// 현재 각 문자열의 문자가 다르면 무조건 N의 인덱스를 증가시켜야 함
	if (O[a] != N[b]) {
		ret = stringDist(a, b + 1, true);
		if (ret != INF && !prev) ret++;
	}
	// 두 문자가 같으면 현재 문자를 포함하거나 포함하지 않음
	else {
		int cand1 = stringDist(a + 1, b + 1, false);
		int cand2 = stringDist(a, b + 1, true);
		if (cand2 != INF && !prev) cand2++;
		ret = min(cand1, cand2);
	}

	return ret;
}

int main() {
	getline(cin, O);
	getline(cin, N);

	// 캐시메모리 초기화
	for (int i = 0; i < 1001; i++) {
		for (int j = 0; j < 1001; j++) {
			cache[i][j] = -1;
		}
	}

	int res = stringDist(0, 0, false);
	if (res >= INF) res = -1;
	cout << res << endl;

	return 0;
}

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

문제

문제

출처

ICPC

dp로 풀었는데 어디서 틀렸을까요?

hssk1528 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말