글 읽기 - 예제 와 질문게시판 반례 모두 맞게 나오는데 틀린 이유를 모르겠습니다

huthealth 4년 전 0

알고리즘은 bottom-up 방식으로

입력 문자열 처음부터 끝까지 펠린드롬을 검사하여 마지막으로 펠린드롬인 인덱스를 저장합니다.

저장된 인덱스가 입력문자열의 마지막 문자를 포함하고있으면 문자열의 처음부터 펠린드롬이 아닌곳까지의 길이를 총 길이에 더해주고( abcc 이면 ab 길이 더해줌)

포함하지 않으면 문자열의 처음부터 저장한 2번째 인덱스 길이까지 더해줍니다 (abacc 이면 aba 길이 더해줌)

답은 제대로 나오는데 뭐가 문제인지 모르겠습니다 ㅠㅜㅠ 질문게시판 반례들도 다 넣어봤습니다

#pragma warning(disable: 4996)
#include<iostream>
#include<string>
using namespace std;

string s;
int dp[1001][1001];

int main() {
	cin >> s;
	int len = s.length();
	int first=len-1, second=len-1;
	int gap = 1;

	for (int i = 0; i < len; i++)
		dp[i][i] = 1;

	for (int i = 0; i + gap < len; i++) {
		if (s[i] == s[i + gap]) {
			dp[i][i + 1] = 1;
			first = i;
			second = i + gap;
		}
	}
	for (gap = 2; gap < len; gap++) {
		for (int i = 0; i + gap < len; i++) {
			if (s[i] == s[i + gap] && dp[i + 1][i + gap - 1]) {
				dp[i][i + gap] = 1;
				first = i;
				second = i + gap;
			}
		}
	}

	if (dp[0][len-1] == 1)
		cout<<0<<endl;
	else {
		if (second == len - 1) {
			cout<< len - second + first - 1+len<<endl;
		}
		else {
			cout << second + 1 + len << endl;
		}
	}
	return 0;
}

myc228 2년 전 0

반례입니다

abbca

정답: 9 (abbcacbba)

출력: 8

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

문제

문제

출처

ICPC

예제 와 질문게시판 반례 모두 맞게 나오는데 틀린 이유를 모르겠습니다

huthealth 4년 전 0

myc228 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말