프로그래머스 - 땅따먹기 / C++

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12913

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

 

문제 풀이

DP를 적용하여 풀면 된다. 주의할 점은 바로 직전의 열이 겹치면 안된다는 것이며 한 행은 항상 4열이다.

따라서, 점화식을 세울 때 해당 행에서 가장 큰 수를 더하되 열이 겹치면 continue해준다.

 

소스 코드

#include <bits/stdc++.h>
using namespace std;

int solution(vector<vector<int> > land)
{
    int answer = 0;
    int n = land.size();
    int DP[100001][4] = { 0, };
    
    for(int i=0; i<4; i++){
        DP[0][i] = land[0][i];
    }
        
    for(int i=1; i<land.size(); i++){
        for(int j=0; j<4; j++){
            int maxVal = -1;
            for(int k=0; k<4; k++){
                if(j==k) continue;
                
                maxVal = max(maxVal, DP[i-1][k]);
            }
            DP[i][j] = land[i][j] + maxVal;
        }
    }
    
    for(int i=0; i<4; i++){
        answer = max(answer, DP[n-1][i]);
    }
    
    return answer;
}