프로그래머스 - 땅따먹기

프로그래머스 - 땅따먹기

dp로 풀 수 있는 문제이다.

dp[i][j]가 의미하는 것은 i행 j열에서 얻을 수 있는 최대 점수이다.
이는 i-1번째 행에서 얻을 수 있는 최대 점수에 (i,j)의 land 값을 더해주면 된다.
같은 열을 연속으로 밟을 수 없기 때문에 이것만 체크해주면 된다.
즉, dp식은 dp[i-1][k] (k != j) + land[i][j]이 된다.

코드는 다음과 같다.

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

using namespace std;

int solution(vector<vector<int>> land)
{
    int answer = 0;
    int row_size = land.size();
    int col_size = land[0].size();
    vector<vector<int>> dp(row_size, vector<int>(col_size, 0));
    for(int j=0;j<col_size;j++)
        dp[0][j] = land[0][j];
    
    for(int i=1;i<row_size;i++) {
        for(int j=0;j<col_size;j++) {
            for(int k=0;k<col_size;k++) {
                if(j == k)
                    continue;
                dp[i][j] = max(dp[i][j], dp[i - 1][k]);
            }
            dp[i][j] += land[i][j];
        }
    }
    answer = *max_element(dp[row_size - 1].begin(), dp[row_size - 1].end());
    return answer;
}