Programers 정수 삼각형

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

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

프로그래머스 정수 삼각형 문제입니다.

 

#include <string>
#include <vector>

using namespace std;
//500 x 500 배열 선언
int dp[501][501];
int maxIdx;
int n,m;

int max(int a,int b){
    return a>b?a:b;
}


int solution(vector<vector<int>> triangle) {
    n = triangle.size();
    m = triangle[n-1].size();
    int maxIdx = 0;
    if(triangle.size() == 1) return triangle[0][0];
    
    dp[0][0] = triangle[0][0];
    for(int i =1;i<triangle.size();i++){
        for(int j = 0;j<=i; j++){
            if(j == 0)
                dp[i][j] = dp[i-1][j] + triangle[i][j];
            else if(j == i){
                dp[i][j] = dp[i-1][j-1] + triangle[i][j];
            }
            else{
                dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + triangle[i][j];
            }
            maxIdx = max(maxIdx, dp[i][j]);
        }
    }
   
    int answer = maxIdx;
    return answer;
}

아이디어

삼각형을 왼쪽으로 몰아놓고 생각을 해야함

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

탑다운 방식으로 점화식을 새워서 풀이 했는데 바텀업방식으로 풀이하면 더 깔끔 할 수 있음