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

문제 설명

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

1932번: 정수 삼각형

 

해결 방법

dp문제이다.

두번째 줄부터 검사할 것이다

 

제일 왼쪽에 있는 경우면 오른쪽 위 대각선 숫자를 더해준다.

제일 오른쪽에 있는 경우면 왼쪽 위 대각섯 숫자를 더해준다.

그 외는 양쪽 대각선 위치에 있는 숫자 중 더 큰것을 더해준다.

마지막 줄에서 가장 큰 수를 구해준다.

#include<iostream>
#include<vector>
using namespace std;

int max(int a, int b)
{
	if (a > b)return a;
	return b;
}

int main() 
{
	//INPUT
	int n; cin >> n;
	vector < vector<int >> triangle(n, (vector<int>(n, -1)));

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



	//SEARCH
	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j <= i; j++)
		{	
			//오른쪽 대각선만 검사
			if (j == 0) { triangle[i][j] += triangle[i - 1][j]; }
			//왼쪽 대각선만 검사
			else if (j == i) { triangle[i][j] += triangle[i - 1][j-1]; }
			//양쪽 대각선 검사
			else { triangle[i][j] += max(triangle[i - 1][j - 1], triangle[i - 1][j]); }
		}
	}


	int maxResult = triangle[n - 1][0];

	for (int i = 1; i < n; i++)
	{
		if (maxResult < triangle[n-1][i])
		{	maxResult = triangle[n - 1][i];	}
	}

	cout << maxResult;

}