[알고리즘 C++] 정수 삼각형

오늘의 문제

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

정수 삼각형

나의 풀이

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    
    vector<vector<int>> dp = triangle;
    for(int i=0;i<triangle.size()-1;i++){
        for(int j =0;j<triangle[i].size();j++){
            dp[i][j] = -1;
        }
    }
    dp[0][0] = triangle[0][0];
    
    for(int i=0;i<triangle.size()-1;i++){
        for(int j =0;j<triangle[i].size();j++){
            int up = dp[i][j];
            dp[i+1][j] = max(dp[i+1][j], up + triangle[i+1][j]);//왼
            dp[i+1][j+1] = max(dp[i+1][j+1], up + triangle[i+1][j+1]);//오
        }
    }
    for(int i=0;i<dp[dp.size()-1].size();i++)
        answer = max(answer, dp[dp.size()-1][i]);
    return answer;
}

모범 답안

#include <string>
#include <vector>

using namespace std;

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

    int temp;
    int Size = triangle.size();
    for (int i = 0; i < Size; ++i)
    {
        temp = 0;
        if (i != Size - 1)
        {
            for (int j = 0; j < triangle[i].size(); ++j)
            {
                if (temp < triangle[i + 1][j] + triangle[i][j])
                    temp = triangle[i + 1][j] + triangle[i][j];

                triangle[i+1][j] = temp;
                if (j != triangle[i].size() - 1)
                    temp = triangle[i + 1][j + 1] + triangle[i][j];
                else
                    triangle[i + 1][j + 1] += triangle[i][j];
            }
        }
        else if (i == Size - 1)
        {
            for (int j = 0; j < triangle[i].size(); ++j)
            {
                if (answer < triangle[i][j])
                    answer = triangle[i][j];
            }
        }
    }

    return answer;
}

배울 점

• 간단한 dp문제였다 3단계는 카카오문제빼고는 2단계와 비슷한듯 하다
• 프로그래머스 60문제 달성! 9월 마지막날에 버저비터 했다