[백준][C++]1932번. 정수 삼각형

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

 

 

삼각형을 2차원 벡터를 통해 입력받고 이 벡터와 크기가 같은 벡터를  선언해주고 이 벡터에 누적합을 계산해서 넣어주면 된다. 이때 현재 층에서 내려갈 때 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서 선택해서 내려가야하는데  내려가있는 입장에서 생각해보면 경우를 나눠서 계산을 해줘야한다.

가장 왼쪽의 경우에는 x-1, y 위치의 원소에 자신의 값을 더해주면 된다.

가장 오른쪽의 경우에는 x-1, y-1 위치의 값에 자신의 값을 더해주면 된다.

가운데의 경우에는  x-1,y-1 와 x-1,y위치 중에 큰 값과 자신의 값을 저해주면 된다.

마지막행에서 최대값을 찾아서 출력해주면 된다.

 

 

정답코드

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n;
	cin >> n;

	vector<vector<int>> triangle(n, vector<int>(n, 0));


	for (int i = 0; i < n; i++)
	{
		for (int j =0; j<=i; j++)
		{
			cin >> triangle[i][j];
		}
		
	}
	
	vector<vector<int>> dp(n, vector<int>(n, 0));

	dp[0][0] = triangle[0][0];

	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			//가장 왼쪽
			if (j == 0)
			{
				dp[i][j] = dp[i - 1][j] + triangle[i][j];
			}
			else if (j == i)	//가장 오른쪽
			{
				dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
			}
			else      //가운데
			{
				dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
			}
		}
	}

	int result = 0;
	for (int i = 0; i < n; i++)
	{
		result = max(dp[n - 1][i], result);
	}

	cout << result << "\n";
}