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

문제 요약

land는 10^(5)행 이하 4열 2차원 배열입니다.
land의 각 열에선 한 자리만 밟을 수 있습니다.
단, 같은 열을 연속적으로 밟을 순 없습니다.
이 때 가장 이득을 많이 볼 때의 이득을 구하세요.

아이디어

DP문제라는 감이 왔다.
f[i][j] = i이전 행들에서 뭘 밟았는진 모르겠지만 여튼 f[i][j]를 마지막으로 밟았을 때의 이득
이라고 정의하였다.
i 이전에 밟았을 것이라고 추정되는 후보들은 조건에 의해 같은 열이 아닌 3개의 이전행 땅일것이다.

여담

효율성 테스트를 통과하지 못하셨다면
int arr[10000][4];
때문일 가능성이 높다

코드

#include <iostream>
#include <vector>
#include<math.h>
using namespace std;

int solution(vector<vector<int> > land) {// dp문제로 접근
    int answer = 0;
    //int arr[10000][4];
    int** arr = new int*[land.size()];
    for(int i = 0;i<land.size();i++){
        arr[i] = new int[4];
        for(int j = 0;j<4;j++){
            arr[i][j] = 0;
        }
    }
    for(int j = 0;j<4;j++){
        arr[0][j] = land[0][j];
    }
    for(int i = 1;i<land.size();i++){
        for(int j = 0;j<4;j++){
            for(int k = 0;k<4;k++){
                if(j != k){
                    arr[i][j] = max(arr[i][j],arr[i-1][k]+land[i][j]);
                }
            }
        }
    }
    answer = *max_element(&arr[land.size()-1][0],&arr[land.size()-1][0]+4);
    /*
    for(int j = 0;j<4;j++){
        answer = max(answer, arr[land.size()-1][j]);
    }
    */
    return answer;
}