Level 3. 정수 삼각형

Level 3. 정수 삼각형

 

 

위에서부터 아래로 내려오면서 좌측 부모, 우측 부모 중 큰 값을 더하는 방식이다.

 

그렇다보니 양쪽에서 인덱스 계산이 다소 번거롭다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    for (int i = 1; i < triangle.size(); ++i)
    {
        for (unsigned j = 0; j < triangle[i].size(); ++j)
        {
            int l_parent = (1 <= j) ? triangle[i - 1][j - 1] : 0;
            int r_parent = (j < triangle[i - 1].size()) ? triangle[i - 1][j] : 0;

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

    return answer;
}

 

반대로 아래에서부터 위로 더하는 방식으로 인덱스 게산도 편하고 훨씬 간단하다.

 

#include <iostream>
#include <vector>

using namespace std;

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