[프로그래머스] [C++] 정수 삼각형 (dp)

1. 문제 

 

정수로 이루어진 삼각형에서

 

맨끝에서부터 맨아래쪽 까지의 경로들에서 거쳐간 숫자의 합중 최대값을 구하여라

 

2. Iterative Dynamic Programming

 

이 문제는 삼각형의 제일 맨 아래부터 두개의 수중 큰 수를 바로 위의 정수에 더하면

 

자연스럽게 triangle[0][0]에 가장 큰값이 들어가게 된다.

 

이것은 반복적 동적계획법으로 재귀적으로도 풀수있지만 메모리가 좀 더 소비된다.

 

3. 코드

 

#include <string>
#include <vector>
 
using namespace std;
 
int solution(vector<vector<int>> triangle) {
    for(int i = triangle.size()-2; i >= 0 ; i--)
        for(int j = 0; j < triangle[i].size(); j++)
            triangle[i][j] += max(triangle[i+1][j], triangle[i+1][j+1]);
    return triangle[0][0];
}

 

 

코딩테스트 연습 - 정수 삼각형 | 프로그래머스 (programmers.co.kr)