프로그래머스 - 정수 삼각형 / C++

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

 

 

문제 풀이

간단한 DP 문제이다.

그림에서는 삼각형이지만 실제 배열로 나타내면

[7]
[3, 8]
[8, 1, 0]
[2, 7, 4, 4]
[4, 5, 2, 6, 5] 의 형태이므로 조금 더 점화식을 세우기 쉽다.

누적 값에 현재 값을 더해나가며 DP 배열을 채워나간다

 

행을 i, 열을 j로 나타내면 [3, 8]에서 3에 더할 수 있는 값은 triangle[i-1][j]에 있는 7이고 8에 더할 수 있는 값은 triangle[i-1][j-1]에 있는 7이다. 다음 행으로 넘어와서 8에서 생각하면 triangle[i-1][j]에 있는 3을 더할 수 있고 1에는 triangle[i-1][j]에 있는 8을 더할 수도 있고 triangle[i-1][j-1]에 있는 3을 더할 수도 있다.

 

따라서, 점화식을 j가 1보다 클 때에는 DP[i][j] = max(DP[i-1][j] + triangle[i][j], DP[i-1][j-1] + triangle[i][j])

0일 때에는 DP[i][j] = DP[i-1][j] + triangle[i][j] 로 세워줄 수 있다.

 

테스트 케이스를 실행시켜보면 DP 배열은 아래와 같이 누적된다.

7 10 15 18 16 15 20 25 20 19 24 30 27 26 24

소스 코드

#include <bits/stdc++.h>
using namespace std;

int solution(vector<vector<int>> triangle) {
    int DP[501][501] = { 0, };
    DP[0][0] = triangle[0][0];
    int ans;
    
    for(int i=1; i<triangle.size(); i++){
        for(int j=0; j<triangle[i].size(); j++){
            if(j >= 1){
                DP[i][j] = max(DP[i-1][j] + triangle[i][j], DP[i-1][j-1] + triangle[i][j]);
            }
            else {
                DP[i][j] = DP[i-1][j] + triangle[i][j];
            }
        }
    }
    
    ans = *max_element(DP[triangle.size() - 1], DP[triangle.size() - 1] + (triangle.size() - 1));
    
    return ans;
}