[Programmers] 땅따먹기

• 문제
  

land 배열의 각 행과 열에 해당 칸을 밟았을 때 최댓값을 저장하는 방법으로 문제를 해결하였다.

n번째 열의 칸을 밟는다고 가정했을 때, 그 이전 열을 돌면서 n번째 열을 제외한 값들 중 최댓값을 더해준다.

• 코드

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

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

    for(int i=1; i<land.size(); i++){
        
        for(int j=0; j<4; j++){
            int a = land[i][j];
            
            for(int k=0; k<4; k++){
                if(k==j) continue;
                land[i][j] = max(land[i][j], a + land[i-1][k]);
            }
        }
    }

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

이전에 비슷한 알고리즘을 접한 적이 있어서 어렴풋이 풀이 방법이 떠오르긴 했는데, 명확하게 생각해내고 코드로 표현해내는 게 힘든 것 같다.