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

문제

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

아이디어

Dynamic Programming

• 해당 레벨에서 합이 가장 큰 경우를 저장해나가면 됨

7
3	8
8	1	0
2	7	4	4
4	5	2	6	5

7
10	15
18	16	15	// 10+1, 15+1 중 큰 16을 저장
20	25	20	19	// 마찬가지로 +7, +4 했을 때 큰 수를 저장
24	30	27	26	24

코드

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    
    vector<vector<int>> DP((int)triangle.size(), vector((int)triangle.size(), 0));
    
    DP[0][0] = triangle[0][0];
    
    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][j] + triangle[i][j];
            else
            {
                DP[i][j] = max(DP[i - 1][j] + triangle[i][j], DP[i - 1][j - 1] + triangle[i][j]);
            }
        }
    }
    
    for (int i = 0; i < DP.size(); ++i)
        answer = max(DP.back()[i], answer);
    
    return answer;
}

마무리

• 이게 어떻게 레벨3? 레벨1 같은데