글 읽기 - 숫자삼각형 문제 , 반례를 모르겠습니다.

skfnxh0124 6년 전 0

점화식 잘 세웠고 틀린거 없는거 같은데 ㅠㅠ..

//맨 아래부터 선택을 해서 dp로 풀어보자.
// 시간 복잡도는 괜찮다.

#include<iostream>

using namespace std;
int**dp; // dp
int**trg; // 삼각형 숫자 정보.
int n;
int**check; //Dp 체크 함수,

int max(int x, int y)
{
	if (x >= y)
		return x;
	else
		return y;
}
void Dp(int x, int y);
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	trg = new int*[n + 1];
	dp = new int*[n + 1];
	check = new int*[n + 1];
	for (int i = 0; i <= n; i++)
	{
		if (i == 0)
		{
			trg[i] = new int;
			dp[i] = new int;
			check[i] = new int;
			continue;
		}
		trg[i] = new int[i+1];
		dp[i] = new int[i + 1];
		check[i] = new int[i + 1];
	}
	trg[0] = 0;
	dp[0] = 0;
	check[0] = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 0; j <= i; j++)
		{
			if (j == 0)
			{
				trg[i][j] = 0;
				dp[i][j] = 0;
				check[i][j] = 0;
				continue;
			}
			
			cin >> trg[i][j];
			dp[i][j] = 0;
			check[i][j] = 0;
		}

			
	dp[1][1] = 7;
	check[1][1] = 1;

	for (int k = 1; k <= n; k++)
		Dp(n, k);
	int Max = dp[n][1];
	for (int i = 1; i <= n; i++)
		if (Max <= dp[n][i])
			Max = dp[n][i];
	
	cout << Max;
	
	
}

void Dp(int x, int y)
{
	if (check[x][y] == 0)
		check[x][y] = 1;
	else
		return;
	if (x >= 2 && x <= n&&(y>=1&&y<=x))
	{
		if (y == 1)
		{
			Dp(x - 1, y);
			dp[x][y] = dp[x - 1][y] + trg[x][y];
		}
		else if (y == x)
		{
			Dp(x - 1, y-1);
			dp[x][y] = dp[x - 1][y-1] + trg[x][y];

		}
		else
		{
		
			Dp(x - 1, y);Dp(x- 1, y - 1);
			dp[x][y] = max(dp[x - 1][y - 1], dp[x - 1][y]) + trg[x][y];
		}
	}
}

djm03178 6년 전 0

62번째 줄이 이상하네요.

skfnxh0124 6년 전 0

아 테스트케이스 첫번째꺼를 그대로 넣었네요 감나합니다...ㅠ

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

문제

문제

출처

ICPC

숫자삼각형 문제 , 반례를 모르겠습니다.

skfnxh0124 6년 전 0

djm03178 6년 전 0

skfnxh0124 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말