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

dp 배열을 생성하여 풀면 된다. 

level_3 라기에는 쉬운 문제여서 어떤식으로 접근하는지만 떠올리면 바로 해결할 수 있는 문제이다. 

 

#접근방법

위의 예제를 통해서 dp배열을 생성하면 밑의 숫자값으로 세팅된다.  

7
10  15
18  16  15
20  25  20  19
24  30  27  26  24

왜 이런 dp 값이 나왔는지에 대해선 아래에 있는 코드를 보고 이해하길 권한다. 

즉, 피라미드 구조에서 dp값을 갱신하기 위해서는 현재 위치에서 바로 위에 
양쪽에 있는 숫자값중 큰 값을 골라서 더해주면 되는 것이다.  

* 끝지점일 경우 바로 위의 dp값을 전달받아 현재값을 더해준다. 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int dp[500][500]; 
int solution(vector<vector<int>> triangle) {
    int answer = 0;
    dp[0][0]= triangle[0][0];      
    for(int i=1; i<triangle.size(); i++){ 
        for(int j=0; j<i+1; 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];     
            if(i==triangle.size()-1)answer = max(answer, dp[i][j]); 
        }      
    }   
    return answer;
}

 

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