[프로그래머스 Lv.2] 땅따먹기

문제는 다음과 같습니다.

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

프로그래머스

풀이 코드는 다음과 같습니다.

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

int solution(vector<vector<int> > land)
{
    int answer = 0;
    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][0],max(land[i][1],land[i][3]));
        land[i+1][3]+=max(land[i][0],max(land[i][1],land[i][2]));
    }
    answer=max(land[land.size()-1][0],max(land[land.size()-1][1],max(land[land.size()-1][2],land[land.size()-1][3])));
    return answer;
}

이 문제의 특징은 행렬에서 이전의 행이 다음 행에 영향을 계속해서 미친다는 점입니다.

문제 설명에서는 모든 수가 한 자릿수여서 쉽게 결정할 수 있지만 같은 행에서 수의 차이가 크게 난다면 예상한 결과와는 다른 결과가 나올 수 있기 때문에 동적 프로그래밍 방법을 사용해야 합니다.

계속해서 누적으로 같은 열에 있지 않는 원소를 더해감으로써 그중 가장 큰 점수를 정답으로 가지는 방식을 선택했습니다.