Programmers Level 2: 땅따먹기(C++)

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

코딩테스트 연습 - 땅따먹기

풀이법

1) DP를 활용해서 푸는 것이 중요한 문제이다.

2) DFS나 For문을 이용해서 문제를 풀 경우 시간 초과가 발생한다. 

3) 단순히 각 행 별로 가장 큰 값을 가져 오는 경우

1 2 3 5

3 2 1 100

1 1 2 3

같은 배열의 경우 5+100+3과 같은 규칙에 어긋나는 경우가 발생하므로

arr 배열을 새로 만들고 여기에 현재까지 나올 수 있는 최대 값을 넣어주었다.

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

int arr[100001][4];

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