정수 삼각형 43105

문제

접근 방법

위에서 아래로 간다면 좌, 우로 나누어지기에 매우 많은 경우의 수가 나올 것이다. 그렇다고 지금 당장 가장 높은 값을 따라가기에는 어떤 수가 기다릴지 모르는 것이다.
반대로 아래에서 위를 확인하면 되겠다고 생각했다. 왼쪽, 오른쪽 중 더 큰 값을 가져와서 더하면 아래 기준에서 제일 큰 값일 테니 말이다.

코드

#include <vector>
using namespace std;

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

풀이

어차피 맨 끝은 맨 끝밖에 선택 못 하기에 조건문으로 해결해주느니 반복문에서 빼주었다. 아래 기준에서 위에 값 왼쪽, 오른쪽 중 더 큰 값을 골라서 아래 값에 더해주는 방식으로 접근하면 된다.
이후 맨 밑부분만 다시 확인하여 제일 큰 수를 반환해주면 된다.