[백준] 1932 정수 삼각형 c++

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

#include<iostream>
#include<algorithm>

using namespace std;

int triangle[501][501];
int dp[501][501];
int main()
{
	int N;
	cin >> N;
	int temp;
	for(int i=0;i<N;i++)
		for (int j = 0; j <= i; j++)
		{
			cin >> temp;
			triangle[i][j]=temp;
			//cin >> dp[i][j];
			if (j == 0)
				dp[i][j] = dp[i - 1][j]+temp;
			else if(j==i)
				dp[i][j] = dp[i - 1][j-1]+temp;
			else
				dp[i][j] = max(temp + dp[i - 1][j - 1], temp + dp[i - 1][j]);
			
		}
	int ans = 0;
	for (int i = 0; i < N; i++)
	{
		if (dp[N - 1][i] > ans)
			ans = dp[N - 1][i];
	}
	cout << ans;

}

dp[i][j]는 i,j까지 도달할수 있는 경로(합)중에 최댓값을 저장하는 배열이다.

j가 0이나 i일때는 위층에서 i,j에서 선택할 수 있는 경우가 하나이기때문에 temp와 더해서 저장해주고

나머지는 두 가지의 경우의 수 중에서 더 큰 경우를 선택한다.

마지막에 N-1 층에 있는 수 중에서 최댓값을 출력한다.