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

#include <string>
#include <vector>

using namespace std;

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

    for (int i = 1; i < triangle.size(); i++)
    {
        int endNum = triangle[i].size() - 1;

        triangle[i][0] += triangle[i - 1][0];
        triangle[i][endNum] += triangle[i - 1][endNum - 1];
        
        answer = max(triangle[i][0], answer);
        answer = max(triangle[i][endNum], answer);

        for (int j = 1; j < endNum; j++)
        {
            int maxNum = max(triangle[i - 1][j - 1], triangle[i - 1][j]);

            triangle[i][j] += maxNum;

            answer = max(triangle[i][j], answer);
        }
    }

    return answer;
}

풀이

1. 가장자리의 수는 바로 위의 수를 더해준다.

2. 현재 자리가 n일 때 위에 있는 수들이 n번째와 n-1번째의 수가 존재할 경우 둘중에 큰 수를 더해준다.

3. 구하면서 최대로 큰 값을 저장해준다.

 

 

 

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

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