[C/C++] programmers Level 2 땅따먹기

 

 

 

코드

 

#include <vector>
#include <algorithm> // *max_element

using namespace std;

int solution(vector<vector<int> > land)
{
    int answer = 0;
    vector<vector<int>> landmax(land.size(),vector<int>(4)); // land.size() : 행, vector<int>(4) : 4열로 고정
    
    for(int i=0;i<4;i++){
        landmax[0][i]=land[0][i]; // 1행 값 삽입
    }
    
    for(int i=1;i<land.size();i++){
        for(int j=0;j<4;j++){
            int maxnum=0; // 행 중에서 가장 큰 값
            
            for(int k=0;k<4;k++){
                if(j==k){ // 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙 : j!=k 조건
                    continue;
                }
                
                if(maxnum<landmax[i-1][k]){ 
                    maxnum=landmax[i-1][k]; // 전 행 중 가장 큰 값을 maxnum에 저장
                }
            }
            
            landmax[i][j]=land[i][j]+maxnum; // 전 행 중 가장 큰 값인 maxnum과 현재 행인 land[i][j]를 더함 --> j==k 일 경우 maxnum=0을 더해줌으로 가장 큰값이 될수 없음
        }
    }
    
    answer=*max_element(landmax[land.size()-1].begin(),landmax[land.size()-1].end()); // 최종 마지막 연산을 다한 바닥 부분에서 가장 큰값을 구함
    
    return answer;
}