알고리즘 스터디 42일차

1. 정수 삼각형

1) 문제

2) 문제 분석 및 풀이

1) 설계, 분석

2) 풀이

#include <string>
#include <vector>

using namespace std;

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

    vector<vector<int>> dp = triangle;

    for (int i=1; i<triangle.size(); i++)
    {
        for (int j=0; j<triangle[i].size(); j++)
        {
            // 맨 왼쪽, 오른쪽 위에서만 올 수 있음.
            if (j == 0) { dp[i][j] += dp[i-1][0]; }
            // 멘 오른쪽, 왼쪽 위에서만 올 수 있음.
            else if (j == triangle[i].size() - 1) { dp[i][j] += dp[i-1][j-1]; }
            // 중간, 양쪽 중에서 최대값을 선택
            else 
            {
                dp[i][j] += max(dp[i-1][j], dp[i-1][j-1]);
            }
        }
    }

    answer = *max_element(dp.back().begin(), dp.back().end());

    return answer;
}