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

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

코딩테스트 연습 - 땅따먹기 | 프로그래머스

 

단순히 DFS나 단순 for문으로 모든 경우를 탐색하는 경우에는 시간초과가 일어난다.

행의 갯수가 100000개라고 가정했을 때

4 * 3 * 3 * 3 * 3 ..... * 3 = 4 * 3^99999의 시간복잡도가 나오기 때문이다.

그렇기 때문에 이 문제는 dp를 사용하여 풀었다

이전의 행, 다른 열에서의 최댓값을 가져온다음 현재 행, 열의 값을 더해주고

마지막에 최댓값만 구해주면 되는 것이다.

 

dp[현재 행][현재 열] = land[현재 행][현재 열] + MAX([dp[이전 행][다른 열들]])

 

열이 4개 밖에 되지 않기 때문에 따로 for문 조건을 만들지 않았다.

 

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


int dp[100001][4];

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