[Algorithm] Programmers :: 땅따먹기

https://school.programmers.co.kr/learn/courses/30/lessons/12913

프로그래머스

int dp[100001][4] = { 0 };
 
int solution(vector<vector<int> > land)
{
    int answer = 0;
 
    int rowSize = land.size();
    
    for (int i = 0; i < 4; ++i)
    {
        dp[0][i] = land[0][i];
    }
 
    for (int i = 1; i < rowSize; ++i)
    {
        dp[i][0] = land[i][0] + max({ dp[i - 1][1], dp[i - 1][2], dp[i - 1][3] });
        dp[i][1] = land[i][1] + max({ dp[i - 1][0], dp[i - 1][2], dp[i - 1][3] });
        dp[i][2] = land[i][2] + max({ dp[i - 1][0], dp[i - 1][1], dp[i - 1][3] });
        dp[i][3] = land[i][3] + max({ dp[i - 1][0], dp[i - 1][1], dp[i - 1][2] });
    }
 
    answer = max({ dp[rowSize - 1][0],dp[rowSize - 1][1], dp[rowSize - 1][2], dp[rowSize - 1][3] });
 
    return answer;
}

DP문제의 연습문제로 추천할만한 문제이다. 

다음 행에선 같은열로는 이동을 못 한다 했으니, 아래로 쭉 업데이트해주면서 해당 칸의 값(land[i][0]) + 그 전 행의 같은열을 제외한값들 중 최대값   으로 dp테이블을 업데이트하면 된다.

 

현재 그냥 c++, 2레벨짜리 풀어보고있는데 유난히 DP문제가 많은듯하다;