프로그래머스 Level 2 땅따먹기

땅따먹기 (프로그래머스 Level 2)

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

처음에는 DFS로 풀 수 있다고 생각하였는데
시간초과가 발생하였다
그렇기에 뭔가 놓치고 있는 부분이 있다 생각하였고
추천 문제에서 이 부분이 알고리즘 강의와 연동되어 있었기에
해설에서 ‘DP’ 문제라 언급하여 해당 부분에서 힌트를 얻어 풀 수 있었다

Code

#include <vector>
using namespace std;

int solution(vector<vector<int> > land)
{
    int answer = 0;

    vector<vector<int>> dp(land.size() + 1, vector<int>(4, 0));

    for (int i = 0; i < land.size(); i++)
    {
        for (int j = 0; j < 4; j++)
        {
            for (int k = 0; k < 4; k++)
            {
                if (j == k)
                    continue;

                if (dp[i + 1][k] >= dp[i][j] + land[i][j])
                    continue;

                dp[i + 1][k] = dp[i][j] + land[i][j];
            }
        }
    }

    for (int i = 0; i < 4; i++)
    {
        if (dp[land.size()][i] > answer)
            answer = dp[land.size()][i];
    }

    return answer;
}