[Programmers] 정수 삼각형

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

 

---

 

문제 해결 과정

착안

동적계획법(dynamic programming)을 통해 가장 아래 층의 숫자들부터 인접한 두 개씩 비교하여 위의 숫자로 더해나가는 방식으로 문제를 해결하고자 하였다.

 

구현

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> triangle)
{
	for (int i = triangle.size() - 1; i > 0; i--)
		for (int j = 0; j < triangle[i].size() - 1; j++)
			triangle[i - 1][j] += triangle[i][j] > triangle[i][j + 1] ? triangle[i][j] : triangle[i][j + 1];

	return triangle[0][0];
}

 

실행 결과