[c++] 프로그래머스 - 땅따먹기(Level 2)

문제

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

 

풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int dp[100001][4];

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

 

풀이(14분)

이 문제를 처음 시도했던 건 한 8개월 전이었던 거 같습니다. 그때는 지금도 부족하긴 하지만 DP개념이 부족해서 그리디로 풀려다가 실패했던 기억이 나네요 

오랜만에 이 문제를 풀어보게 되었는데 손쉽게 풀려서 성장한 것 같아 기분이 좋습니다.

아래의 입출력으로 설명을 해보겠습니다.

land	answer
[[1,2,3,5],[5,6,7,8],[4,3,2,1]]	16

 

if(k==0) dp[i][k] = max({dp[i-1][k+1],dp[i-1][k+2],dp[i-1][k+3]})+land[i][k];
if(k==1) dp[i][k] = max({dp[i-1][k-1],dp[i-1][k+1],dp[i-1][k+2]})+land[i][k];
if(k==2) dp[i][k] = max({dp[i-1][k-2],dp[i-1][k-1],dp[i-1][k+1]})+land[i][k];
if(k==3) dp[i][k] = max({dp[i-1][k-3],dp[i-1][k-2],dp[i-1][k-1]})+land[i][k];

한 행씩 내려오면서 같은 열은 밟을 수 없다는 제약 조건이 있기 때문에 본인의 이전 열을 제외한 나머지 누적 합 중 가장 큰 것을 현재 land값과 더해주고, 마지막에 제일 큰 값을 출력하면 됩니다.