[프로그래머스LV2] 땅따먹기 (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/12913

프로그래머스

 

처음엔 백트래킹으로 구현했는데 시간초과가 났다. 4^10만이기 때문에 말도안되는 시도였다.

그래서 DP를 생각했고 백트래킹에 접목했는데 틀렸다. 그리고 좀 더 유심히 문제를 보니 열은 반드시 4로 주어지는 문제였다. 그래서 Bottom-Up 방식 DP를 생각해냈다.

 

결국 i번 행에서는 i - 1행의 3가지 경우 중 하나만 올 수 있고 그 중 최댓값을 구하면 되기 때문이다.

 

그래서 다음과 같은 점화식이 생긴다.

 

DP[i][j] = value[i][j] + max(DP[i - 1[j + 1], DP[i - 1][j - 1], DP[i - 1][j - 2])

 

여기서 j를 뺀 세가지가 위 max안에 들어가고 코드는 매우 간단해진다.

 

#include <iostream>
#include <vector>
using namespace std;
int dp[100001][4];
int solution(vector<vector<int> > land)
{
    int answer = 0;
    
    for(int i = 1; i <= land.size(); i++){
        dp[i][0] += land[i - 1][0] + max(max(dp[i - 1][1], dp[i - 1][2]), dp[i - 1][3]);
        dp[i][1] += land[i - 1][1] + max(max(dp[i - 1][0], dp[i - 1][2]), dp[i - 1][3]);
        dp[i][2] += land[i - 1][2] + max(max(dp[i - 1][0], dp[i - 1][1]), dp[i - 1][3]);
        dp[i][3] += land[i - 1][3] + max(max(dp[i - 1][0], dp[i - 1][1]), dp[i - 1][2]);
    }

    return max(max(dp[land.size()][0],dp[land.size()][1]), max(dp[land.size()][2],dp[land.size()][3]));
}