글 읽기 - 반례가 뭐가 있을까요?

kyunghooh76 4년 전 0

반례를 못찾겠는데, 체줄하면 얼마 지나지 않아 바로 실패 합니다. ㅠ.ㅠ

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int N;
int value[1000][1000];
int cache[1000][1000];
int maxTrangle(int y, int x)
{
	if (y == N) return 0;
	int& ret = cache[y][x];
	if (ret != -1) return ret;
	ret = max(maxTrangle(y + 1, x), maxTrangle(y + 1, x + 1)) + value[y][x];

	return ret;
}
int main(int argc, char** argv)
{
	int nCount;
	memset(cache, -1, 1000 * 1000);
	memset(value, 0, 1000 * 1000);
	scanf("%d", &nCount);
	N = nCount;
	for (int i = 0; i < nCount; i++) {
		for (int j = 0; j <= i; j++)
			scanf("%d", &value[i][j]);
	}

	cout << maxTrangle(0, 0) << endl;

	return 0;
}