프로그래머스 땅따먹기

 

 

삼각형 문제랑 같다.

dp 문제이다

 

#include <iostream>
#include <vector>
#define MAX(a, b) ((a >= b) ? a : b)

using namespace std;

int solution(vector<vector<int> > land)
{
    int answer = 0;
    
    int row = land.size();
    int left, right;
    
    vector<vector<int>> dp(land.begin(), land.end());
    
    
    for(int i = 1; i < row; i++) {
        
        
        for(int j = 0; j < 4; j++) {
            
            int max = 0;

            for(int k = 0; k < 4; k++) {
                
                if(k != j && max < dp[i - 1][k]) {
                    max = dp[i - 1][k];
                }
            }
            
            dp[i][j] += max;
            
            answer = MAX(answer, dp[i][j]);
            
        }        
    }
    

    return answer;
}