[알고리즘] DP- 땅따먹기

#include<iostream>
#include<vector>
using namespace std;
 
 
vector<vector<int>> dp(10001, vector<int>(4,0));
 
int hopscotch(vector<vector<int> > board)
{
    // 함수를 완성하세요.
    
    // if (x != z)
    // d[n][x] = max(d[n-1][z]) + board[n][z] 
    // 점화식[?]
 
    int answer = 0;
    int col =  4;
      int row = board.size();
    int tmp = 0;
  for(int i = 0 ; i < 4; i++)
        dp[0][i] = board[0][i];
 
  for (int y = 1 ; y < row ;y++ )
  {
            for ( int x = 0 ; x < col ;x++)
            {
                tmp = 0;
                for(int z = 0 ; z < col ; z++)
                {
                    //구하고자 하는 이전 합의 최댓값 
                    if(x != z){
                        if( tmp < dp[y-1][z])
                            tmp = dp[y-1][z];
                    }
                }
                dp[y][x] = tmp + board[y][x];
            }
    }
 
/* Debug
    for (int i = 0 ; i < row; i++)
    {
        for( int x= 0 ; x < 4; x++)
        {
            cout << dp[i][x] << ' ';
        }
        cout << endl;
    }
*/
 
    for(int i = 0 ; i < 4;i++)
    {
            if(answer < dp[row-1][i])
            answer = dp[row-1][i];
    }
 
    return answer;
}
 
int main()
{
    vector<vector<int> > test{
                                                        {1,2,3,5},
                                                        {13,6,7,8},     //  10    9  12 11
                                                        {4,3,5,1},     // 16    15 13 13
                                                        {8,1,2,3},  // 1015  17 18 19
                                                        {10,2,2,3},  // 2019
                                                        {1,8,2,3}};
 //아래는 테스트로 출력해 보기 위한 코드입니다.
    cout << hopscotch(test);
}