글 읽기 - [C] 반례를 알려주세요 ㅠ

brian0926 2년 전 0

카탈란 수 점화식 Cn = 2nCn / (n+1) = (2n)! / n!(n+1)!을 사용했는데 반례를 찾지 못하겠습니다 ㅠㅠ

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

long long int arr[5001];

long long cat(int n)
{
	arr[1] = 1;
	if (arr[n] != 0)
		return arr[n];
	else
	{
		arr[n] = (cat(n - 1) * (2 * n) * (2 * n - 1) / (n * (n + 1))) % 1000000007;
		return arr[n];
	}
    //카탈란 수 점화식
}

int main()
{
	int t;
	scanf("%d", &t);

	for (int i = 0;i < t;i++)
	{
		int l;
		scanf("%d", &l);
		if (l % 2 == 1)
			printf("0\n");
		else
			printf("%d\n", cat(l/2));
	}

	return 0;
}

junah 1년 전 0

@brian0926

카탈란 수 없이 직접 DP 점화식을 구해서 풀어서 잘 모르겠지만

N이 1부터 20까지의 값은 아래와 같습니다.

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

문제

문제

출처

ICPC

[C] 반례를 알려주세요 ㅠ

brian0926 2년 전 0

junah 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말