[C++] 땅따먹기 - DP

 

땅따먹기

문제 유형

이 문제는 DP(동적 계획법) 문제다.

조건은 같은 열을 연속해서 선택할 수 없다는 것이다.

같은 행을 계속 밟을 수 없음 ❌
같은 열을 연속해서 선택할 수 없음 ✅

DP 상태

dp[i][j]를 다음과 같이 정의한다.

i번째 행에서 j번째 열을 선택했을 때 얻을 수 있는 최대 점수

점화식

현재 j번째 열을 선택하면 이전 행에서는 j가 아닌 열을 선택해야 한다.

dp[i][j] =
    land[i][j] + 이전 행에서 j가 아닌 열의 최댓값

예를 들어 현재 j = 2열을 선택하면 이전 행에서는:

0열, 1열, 3열

중 하나를 선택해야 한다.

초기값

첫 번째 행은 이전 행이 없으므로 그대로 저장한다.

dp[0][j] = land[0][j];

풀이 코드

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> land) {
    int n = land.size();

    vector<vector<int>> dp(n, vector<int>(4, 0));

    // 첫 번째 행
    for (int j = 0; j < 4; j++) {
        dp[0][j] = land[0][j];
    }

    // 두 번째 행부터 계산
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < 4; j++) {
            int best = 0;

            for (int k = 0; k < 4; k++) {
                if (k != j) {
                    best = max(best, dp[i - 1][k]);
                }
            }

            dp[i][j] = land[i][j] + best;
        }
    }

    // 마지막 행에서 가장 큰 값이 정답
    return *max_element(dp[n - 1].begin(), dp[n - 1].end());
}