[Lv 2] 땅따먹기

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

프로그래머스

 

이 문제는 제귀를 사용한 반복으로 해결할 수 없다. 이유는 돌아가는 상황으로 인해 O(N^2)이 일어날 수 있기 때문이다.

 

따라서 dp를 사용해서 해결할 수 있다.

초기 dp배열의 0번째 행 위치에 land의 0번째 행의 4개 요소를 집어 넣는다.

 

이후 land배열을 1번째 행부터 순회를 시작한다.

단, 0번째 행의 최대 요소를 찾아야한다. 이때 1번째 행에서 선택한 열은 최대 값을 계산하는데 사용하지 않는다.

dp에 계속해서 누적하면 배열의 마지막 위치에는 최대 값이 존재하게 된다.

 

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