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

👓 문제 설명

---

문제 설명

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

---

💣 제한 사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

---

🚨 접근 방법

전형적인 DP 문제이다.
처음에는 삼각형의 꼭대기부터 맨 아래층으로 DP를 하려고했다.
그러나 맨 아래 층에서 다시 한번 max값을 찾아줘야 하는 번거로움이 생겼다.
그래서 맨 아래층부터 꼭대기로 DP를 하면 dp[0][0]에 하나의 정답만 존재하기 때문에 이 방법으로 수정했다.

---

🚈 풀이

#include <string>
#include <vector>
#include <iostream>
using namespace std;

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

    vector<vector<int>>dp(n,vector<int>(n,0));
    
    for(int i=0;i<n;i++){
        dp[n-1][i]=triangle[n-1][i];
    }
    
    for(int i=n-2;i>=0;i--){
        for(int j=0;j<=i;j++){
            dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+triangle[i][j];
        }
    }
    
    answer=dp[0][0];
    return answer;
}