C++ 프로그래머스 정수삼각형

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

프로그래머스

풀이

DP문제로  따로 DP배열을 안 만들고 기존 배열에 덮어가며 구현했다.

 

주어진 배열에서 

2행 초기화

3행부터는 

중간에 값들은 전행의 왼쪽, 오른쪽 값 중 큰 값과 더해주었다.

 

마지막 열까지 더해준 후에, 마지막열에서 가장 큰 값을 찾으면 그것이 정답 !

---

#include <algorithm>
#include <vector>


using namespace std;
int solution(vector<vector<int>> triangle) {
    int answer = 0;
    for (int i = 1; i < triangle.size(); i++) {
        for (int j = 0; j < triangle[i].size(); j++) {
            if (j == 0) { // 처음
                triangle[i][j] += triangle[i - 1][j];   
            }
            else if (j == triangle[i].size() - 1) { // 마지막
                triangle[i][j] += triangle[i - 1][j - 1];
            }
            else { //바로 위 왼쪽 오른쪽 중에 큰 것과 더하기
                triangle[i][j] += max(triangle[i - 1][j-1], triangle[i - 1][j]);
            }

        }
    } // for
    int tri_size = triangle.size() - 1; // 마지막행
    for (int i = 0; i < triangle[tri_size].size(); i++) {
        if (answer < triangle[tri_size][i]) // 최댓값 찾기
            answer = triangle[tri_size][i];
    }

    return answer;
}