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

문제

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

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

풀이

지금까지의 경로의 합 중 최댓값을 저장해놓은 배열을 DP라고 선언합니다.

DP는 다음과 같은 규칙을 따릅니다.

1. 줄의 첫 칸 일 경우 : 자신의 DP값 = 전 줄의 첫 칸의 DP값 + 자신의 값

2. 줄의 마지막 칸 일 경우 : 자신의 DP값 = 전 줄의 마지막 칸(j-1)의 DP값 + 자신의 값

3. 그 외의 경우 : 자신의 DP값 = 전 줄의 j-1, j번째 DP값 충 더 큰 값 + 자신의 값

삼각형의 값은 0이상이므로 마지막 줄인 경우에만 최댓값을 갱신해주면 됩니다.

소스 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int dp[501][501];
 
int solution(vector<vector<int>> triangle) {
    int answer = 0;
    dp[0][0] = triangle[0][0];
    // 삼각형 2째줄부터 탐색
    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 if (j == triangle[i].size() - 1) {
                dp[i][j] += dp[i - 1][j - 1] + triangle[i][j];
            }
            // 중간 칸
            else {
                int temp = max(dp[i - 1][j - 1], dp[i - 1][j]);
                dp[i][j] += temp + triangle[i][j];
            }
            // 마지막 줄이라면 최댓값 갱신
            if (i == triangle.size() - 1) {
                answer = max(answer, dp[i][j]);
            }
        }
    }
    return answer;
}