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

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

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

코드

#include <string>
#include <vector>
 
using namespace std;
int dp[501][501];
int solution(vector<vector<int>> triangle) {
    int n = triangle.size();
    dp[0][0] = triangle[0][0]; 
    for (int i = 1; i < n; i++) {
        dp[i][0] = dp[i - 1][0] + triangle[i][0];
        for (int j = 1; j <= i; j++) {
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) ans = max(ans, dp[n - 1][i]);
    return ans;
}

 

풀이

출처: 프로그래머스

맨 첫 줄의 7의 거쳐간 숫자의 합은, 자기 자신밖에 없으므로 7입니다.

 

두 번째 줄인 3과 8은, 7에서만 갈 수 있으므로, 3과 8까지의 거쳐간 숫자의 합은 각각 10, 15입니다.

 

그 다음 줄에는 8, 1, 0이 있습니다.

8은 3에서만 갈 수 있고, 3까지의 거처간 숫자의 합이 10이므로, 10 + 8을 해주면 8까지의 거쳐간 숫자의 합은 18입니다.

그리고 0은 8에서만 갈 수 있고, 8까지의 거쳐간 숫자의 합은 15이므로, 15 + 0을 해주면 0까지 거쳐간 숫자의 합은 15입니다.  

그런데 세 번째 줄의 중간에 있는 1은 3 혹은 8에서 갈 수 있습니다. 

3과 8의 거쳐간 숫자의 합은 10과 15이니, 더 큰 15를 더 해 주면, 1까지 거쳐간 숫자의 합은 16이 됩니다.

 

이를 반복해서 구현해 주면 문제를 풀 수 있습니다.