글 읽기 - dp로 풀었는데 틀렸습니다.

pkc4913 4년 전 0

점화식은

dp[i][j] : i부터 j까지 수를 썼을때 나올수 있는 경우의 수

dp[i][j] = dp[i + 1][j] + dp[i][j - 1]

입니다

어디가 틀렸을까요??

#include <bits/stdc++.h>
using namespace std;

int dp[11][11], A[11];
char B[11];
int solve(int from, int to) {
	if (from + 1 == to) {
		if (A[from] != A[to]) return 2;
		else return 1;
	}
	if (from == to) return 1;
	int &ret = dp[from][to];
	if (ret != -1) return ret;
	ret = 0;
	if (A[from] == A[to]) ret = solve(from + 1, to - 1);
	else ret = solve(from, to - 1) + solve(from + 1, to);
	return ret;
}
int main() {
	memset(dp, -1, sizeof(dp));
	scanf("%s", B);
	int size_B = strlen(B);
	for (int i = 0; i < size_B; i++)
		A[i] = B[i] - '0';
	if (size_B == 1) {
		printf("1"); return 0;
	}
	else if (size_B == 2) {
		if (A[0] == A[1]) printf("1");
		else printf("2");
		return 0;
	}
	printf("%d", solve(0, size_B - 1));
}

adh0463 4년 전 0

문자가 연속적으로 같은 경우를 고려하지 않으셨네요.

반례 드립니다.

in :  21112
out:  8

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

문제

문제

출처

ICPC

dp로 풀었는데 틀렸습니다.

pkc4913 4년 전 0

adh0463 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말