C++:: 프로그래머스 < 땅따먹기 >

문제의 핵심은 이전까지의 최대합중 같은 열을 제외한 가장 큰 값들을 계속 구해가다 마지막에 가장 큰값을 골라주면 된다는 점이다.

#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<vector<int> > land) {
    int answer = 0, size = land.size();
    vector<vector<int> > dp(size, vector<int>(4, 0));
    for (int i=0; i<4; i++) dp[0][i] = land[0][i];// 시작 
    for (int i=1; i<size; i++) {
        for (int j=0; j<4; j++) {
            int prev_max = 0;
            for (int k=0; k<4; k++) {// 이전 dp들중 가장 큰값 구하기
                if (k == j) continue ;
                prev_max = max(prev_max, dp[i-1][k]);
            }
            dp[i][j] = prev_max + land[i][j];// 이전 dp중 가장 큰값 + 현재값
        }
    }
    for (int i=0; i<4; i++) answer = max(answer, dp[size-1][i]);// 마지막 값들중 가장 큰값
    return answer;
}

조건에 따른 더 간단한 풀이도 참조한다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int> > land {

    for(int i = 0; i < land.size() - 1; i++) {
        land[i + 1][0] += max(land[i][1], max(land[i][2], land[i][3]));
        land[i + 1][1] += max(land[i][0], max(land[i][2], land[i][3]));
        land[i + 1][2] += max(land[i][1], max(land[i][0], land[i][3]));
        land[i + 1][3] += max(land[i][1], max(land[i][2], land[i][0]));  
    }

    return *max_element(land[land.size() - 1].begin(), land[land.size() - 1].end());
}