[Programmers] C++ LV2_땅따먹기

#사람마다 푼 방법이 다릅니다. 아 이런 코드도 있구나라는 생각만 가져주시면 감사하겠습니다. 제 코드에 있어서 비효율적인 부분이 있으면 댓글로 남겨놔주시면 참고하여 성장할 수 있도록 하겠습니다!!!

 

하지만!!! 무분별한 비난은 삼가해주세여!

 

해당 문제는 처음에는 dfs 풀려고 하다보니까 시간초과가 나더라구요...!!!!! 그래서 생각해보니까 DP로 풀 수 있다고 생각했습니다.

 

0번 행이 아닌 1번행부터 진행하면서 자기 자신과 전 행의 자기 열을 제외한 다른 열들을 더해서 비교했을 때 최댓값을 자기 자신의 값으로 만드는 방법입니다.

#include<iostream>
#include<vector>

using namespace std;

int solution(vector<vector<int> > temp)
{
    int answer = -1;
	vector<vector<int>> land = temp;
    //1번 row 부터 row -1과 더해가면서 비교해가야한다.
    for(int row = 1;row<land.size();row++){
        //현재 row의 열
        for(int col = 0;col<4;col++){
            int max = -1;
            //row-1 행의 열
            for(int pre = 0;pre<4;pre++){
                if(pre == col) continue;
                if((temp[row][col] + temp[row-1][pre]) > max){
                    max = temp[row][col] + temp[row-1][pre];
                }
            }
            temp[row][col] = max;
        }
    }
    //마지막 행의 열들 중 최댓값이 답이 된다.
    for(int a = 0;a<4;a++){
        if(answer<temp[temp.size()-1][a]){
            answer = temp[temp.size()-1][a];
        }
    }
    return answer;
}