글 읽기 - 정수 삼각형 반례가 있을까요?

yongzino 5년 전 0

안녕하세요.

검색해보면 제일 윗층에서 아래로 내려오면서 누적합의 최대값을 구하는 코드가 많긴한데

저는 맨 아래에서 위로 올라가면서 최대값을 구해 맨위층에 있는 값을 출력하는 형식으로 코드를 작성했습니다.

테스트 케이스를 따로 만들어서 실행해보아도 맞는걸로 나오는데..

어떤 반례가 있을지 궁금해서 글을 남깁니다.

#include <stdio.h>
long long int max(long long int a, long long int b)
{
	return a > b ? a : b;
}
int main()
{
	long long int tri[501][501] = { 0 };
	long long int dp[501][501] = { 0 };
	int n,i,j;
	scanf("%d", &n);

	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= i; j++)
		{
			scanf("%d", &tri[i][j]);
		}
	}

	for (i = n; i >= 1; i--)
	{
		for (j = 1; j <= i; j++)
		{
			dp[i][j] = tri[i][j]+max(dp[i + 1][j], dp[i + 1][j + 1]);
		}
	}

	printf("%lld\n", dp[1][1]);
	return 0;
}

djm03178 5년 전 0

반복문이 불필요한 범위, 즉 삼각형의 바깥까지 계산하고 있습니다. 바깥으로 안 나가게 범위 조정을 잘 하거나, 아니면 dp의 크기만 키워도 통과됩니다.

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

문제

문제

출처

ICPC

정수 삼각형 반례가 있을까요?

yongzino 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말