글 읽기 - 맞추긴 했는데 좀 꺼림직한 부분이 있는데요

dydsj0920 6년 전 1

어쩌다 맞추긴 했는데 정확히 맞췄다는 느낌이 없어서요..저는 개인적으로

1. d[0] = 1로 해줘야 한다고 생각하는데..잘못 생각한건가요?
(d[i] 는 문자열s에서 i번째 문자열 까지의 펠린드롬 분할 개수의 최소값) => s의 0번째 문자열에는 최소 1개가 있으니까 d[0] = 1

2. 44번째 배열 인덱스 j-1이 음수가 나오는 상황을 피했으면 좋겠는데

1번과 2번을 동시에 만족해서 코드를 수정하려면 어떻게 해야할까요? 2번을 추가적으로 수정하려고 하면 계속해서 틀린답이 나오네요.

#include <iostream>
#include <string>
#include <cstring>

using namespace std;

bool c[2500][2500];
int d[2500];

int main()
{
	string s;
	cin >> s;

	int n = s.length();

	for (int i = 0; i < n; i++) {
		c[i][i] = true;
	}

	for (int i = 0; i < n - 1; i++) {
		if (s[i] == s[i + 1]) {
			c[i][i + 1] = true;
		}
	}

	//길이k
	for (int k = 3; k <= n; k++) {
		for (int i = 0; i <= n - k; i++) {
			int j = i + k - 1;
			if (s[i] == s[j] && c[i + 1][j - 1]) {
				c[i][j] = true;
			}
		}
	}

	memset(d, -1, sizeof(d));

	d[0] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			if (c[j][i]) {
				if (d[i] == -1 || d[i] > d[j - 1] + 1) {
					d[i] = d[j - 1] + 1;
				}
			}
		}
	}
	printf("%d\n", d[n - 1]);

	return 0;
}

joy144 4년 전 0

d[2501]으로 잡고

d[0] = 0;

d[1] = 1;로 잡으면

-1에 걸릴일도 없을거고, j - 1가 음수가 되서 망하는 일도 없을거고,

d[0]가 0이니까 DP[i] > DP[j - 1] + 1이랑 DP[i] = DP[j - 1] + 1;에도 문제를 안일으키더라구요

소스 일부를 놓고갈게요

	vector<int> DP(textSize + 1, -1);
	DP[0] = 0;
	DP[1] = 1;
	for (int i = 2; i < textSize + 1; i++) {
		for (int j = 1; j <= i; j++) {
			if (dp[j-1][i-1]) {
				if (DP[i] == -1 || DP[i] > DP[j - 1] + 1) {
					DP[i] = DP[j - 1] + 1;
				}
			}
		}
	}

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

문제

문제

출처

ICPC

맞추긴 했는데 좀 꺼림직한 부분이 있는데요

dydsj0920 6년 전 1

joy144 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말