최근 풀이

: dfs로 접근할까? 생각을 했지만, 인자가 복잡해질 것 같음..
규칙을 만들어서 접근하면 될것 같다고 생각을 함.

-> 맨 앞과 맨뒤의 인덱스 따로 처리하고 , 중간값은 최대값으로 설정하자.

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


int mmax = 0;
int n;

int main() 
{
	//자기 인덱스 와 동일한 인덱스 
	// 자기 인덱스 + 1 만큼의 인덱스 

	cin >> n;

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

	//cout << "input" << endl;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j <  i + 1; ++j)
		{
			cin >> v[i][j];
		}
	}
	/*
	cout << "output" << endl;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < i + 1; ++j)
		{
			cout << v[i][j] << " ";
		}
		cout << endl;
	}
	*/
	/*
	v[1][0] += max(v[0][0], v[0][1]);
	v[1][1] += max(v[0][0], v[0][1]);

	v[2][0] += max(v[1][0], v[1][1]);
	v[2][1] += max(v[1][0], v[1][1]);
	*/
	//v[1][0] += v[0][0];
	//v[1][1] += v[0][0];
	//
	//v[2][0] += v[1][0];
	//v[2][1] += max(v[1][0], v[1][1]);
	//v[2][2] += v[1][1];
	//
	//v[3][0] += v[2][0];
	//v[3][1] += max(v[2][0], v[2][1]);
	//v[3][2] += max(v[2][1], v[2][2]);
	//v[3][3] += v[2][2];

	for (int i = 1; i < n; ++i)
	{
		for (int j = 0; j <= i; ++j)
		{
			if(j == 0)
				v[i][j] += v[i - 1][j];
			else if (i == j)
			{
				v[i][j] += v[i - 1][j - 1];
			}
			//가운데 값.
			else
			{
				v[i][j] += max(v[i - 1][j - 1], v[i - 1][j]);
			}
		}
	}

	//cout << "out put" << endl;
	//for (int i = 0; i < n; ++i)
	//{
	//	for (int j = 0; j < n; ++j)
	//	{
	//		cout << v[i][j] << " ";
	//	}
	//	cout << endl;
	//}

	cout << *max_element(v[n - 1].begin(), v[n - 1].end());
}

풀이전략

: 다이나믹 프로그래밍을 이용함
1) 행렬을 어떻게 구성할까? 생각을 했다.
가운데부터 그려나갈까?
-> 그러기엔 행렬을 나타내는 표가 너무 작다.

2) (0,0)부터 시작하다.

(0,0)
(1,0)(1,1)
(2,0)(2,1)(2,2)
(3,0)(3,1)(3,2)(3,3)
(4,0)(4,1)(4,2)(4,3)(4,4)
이런식으로 그렸고,

3) 규칙성을 찾자

• (first, second) 라고 했을때
  a)second == 0 일때와
  b)second == 마지막 인덱스 일때
  c)그 이외의 값들에 대한 처리

a,b,c를 구분지어서 작성하면된다.

끄적끄적

소스코드

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


int main() {

	int n;	
	cin >> n;
	vector<vector<int>>dp(n + 1, vector<int>(n + 1, 0));
	vector<vector<int>>input(n + 1, vector<int>(n + 1,0));

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


	//dp[0][0] = input[0][0];
	for (int first = 1; first < n; first++)
	{
		for (int second = 0; second <= first; second++)
		{
			if (second != 0 && second != first)
			{
				dp[first][second] = max(dp[first][second] +dp[first - 1][second -1], 
					dp[first][second] + dp[first - 1][second]);
			}
			else if(second == 0)
			{
				dp[first][second] += dp[first - 1][second];
			}
			else if (second == first)
			{
				dp[first][second] += dp[first - 1][second - 1];
			}
		}
	}

	int max = 0;
	for (int i = 0; i < n; i++)
	{
		if (max < dp[n - 1][i])
			max = dp[n - 1][i];
	}
		
	cout << max;
	
	return 0;
}