[C++/알고리즘] 프로그래머스 (정수삼각형 )

programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

 

 

앞서 풀었던 문제 중 땅따먹기와 개념이 비슷한 문제이다. 

 

int Find_max(int n1, int n2)
{
	return n1 > n2 ? n1 : n2;
}

int solution(vector<vector<int>> triangle) {
	int answer = 0;

	int triangle_size = triangle.size();

	for (int i = 0; i < triangle_size-1; ++i)
	{
		for (int j = 0; j < triangle[i+1].size(); ++j)
		{
			if (j < 1 || (j == triangle[i + 1].size() - 1))
			{
				// 왼쪽 끝// 오른쪽 끝 
				if (j < 1)
				{
					triangle[i + 1][j] += triangle[i][0];
				}
				else
				{
					triangle[i + 1][j] += triangle[i][j-1];
				}
				
			}
			else
			{
				triangle[i + 1][j] += Find_max(triangle[i][j - 1], triangle[i][j]);
			}
		}
	}
	
	answer = triangle[triangle_size - 1][0];
	for (int i = 1; i < triangle[triangle_size - 1].size(); ++i)
	{
		if (answer < triangle[triangle_size - 1][i])
		{
			answer = triangle[triangle_size - 1][i];
		}
	}

	return answer;
}