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

✅ LV. 3
🔖 DP

✏️ 1차 솔루션

dfs 로 구현

1. 높이가 1인 삼각형의 경우 1개 숫자를 바로 return
2. 대각선인 노드로 계속 dfs 탐색
   1) 노드 탐색할 때마다 cnt++
   2) 바닥에 도달하면 answer 에 최대 cnt 비교해서 저장
3. dfs 탐색 들어가기 전에 탐색할 루트의 노드 숫자를 cnt 에 더해주고 탐색 이후에는 cnt 에서 그대로 빼주기

🚨 1차 trouble

솔직히 완전탐색과 다를 바 없어서 비효율 끝판왕
top-down 방식으로 했을 때, 무조건 최댓값으로만 더해간다고 해도 최종적인 최댓값이 나오는 것은 아니기 때문에 어떻게 해야할지 모르겠음

✏️ 최종 솔루션

1. 모든 숫자에 대해서 숫자까지 도달하는 데 최댓값을 저장해가면서 최댓값 산출
2. 아랫층으로 넘어가기 전에 아랫층 숫자에 대한 최댓값을 산출해주는 것이 아니라 현재층을 기준으로 윗층의 경로 정해주기
   1) 2층부터 계산 시작
   2) 각 층의 첫번째, 마지막 숫자는 윗층에서 내려올 수 있는 숫자가 하나 뿐이므로 하나의 숫자를 각 숫자의 dp 에 저장
   3) 그 이외의 숫자들은 대각선 위 숫자와 대각선 아래 숫자 중에 큰 값을 dp 에 저장
   4) 마지막으로 현재 숫자(triangle 값)를 dp 에 저장
3. 마지막 층의 dp 값들 중에서 최댓값을 answer 로 지정

📌 self feedback

현재 층을 기준으로 다음 경로를 정하는 것이 아니라 현재 숫자가 최댓값을 가지려면 어떤 경로로 와야하는지 산출

✏️ 최종 code

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int n = triangle.size() - 1;
    int answer = 0;
    int dp[501][501];
    dp[0][0] = triangle[0][0];
    
    for(int i = 1 ; i <= n ; i++) {
        for(int j = 0 ; j <= i ; j++) {
            if(j == 0) { // 첫번재 숫자
                dp[i][j] = dp[i-1][j];
            }
            else if(j == i) { // 마지막 숫자
                dp[i][j] = dp[i-1][j-1];
            }
            else {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]);
            }
            dp[i][j] += triangle[i][j];
        }
    }
    
    // answer 산출
    for(int i = 1 ; i <= n ; i++) {
        if(dp[n][i] > answer) {
            answer = dp[n][i];
        }
    }
    
    return answer;
}