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

1. 문제

---

 

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

 

 

2. 소스코드

---

- 이 문제는 그리디로 풀면, 당연히 최적해를 보장하지 않는다.

- 완전 탐색을 하자니, 열은 4개지만, 행의 개수가 10만이다. 완전 탐색도 불가. 

- 그래서 DP 구나 싶었다.

- [x][y]까지의 최대값은 [x][y] + [x-1]행에서의 최대값 이다. (단, 열은 달라야한다)

 

소스코드

#include <iostream>
#include <vector>
using namespace std;

int dp[100001][4];

int solution(vector<vector<int> > land)
{
    int answer = 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){
            for(int k = 0; k < 4; ++k){
                if(j == k) continue;
                if(dp[i][j] < land[i][j] + dp[i - 1][k])
                    dp[i][j] = land[i][j] + dp[i - 1][k];
            }
        }
    }
    
    int len = land.size();
    cout << len;
    for(int i = 0 ; i < 4; ++i){
        if(answer < dp[len - 1][i])
            answer = dp[len - 1][i];
    }

    return answer;
}