[프로그래머스]연습문제 : 땅따먹기(level 2)(c++)

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

코딩테스트 연습 - 땅따먹기

 

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

using namespace std;

const int MAX_ROW = 100000;
const int MAX_COLUMN = 4;
int dp[MAX_ROW + 1][MAX_COLUMN];

// 주어진 배열에서 한 인덱스를 제외하고 나머지 값 중 최대값 구하기
int get_max_except(const int row[], const int except)
{
    int max = 0;
    for (int i = 0; i < MAX_COLUMN; ++i)
    {
        if (i != except && max < row[i])
        {
            max = row[i];
        }
    }
    return max;
}

int solution(vector<vector<int>> land)
{
    /*
        점화식
        dp[i][j] : land[i][j]를 포함하는 경우의 최대값

        --> dp[i][j] = max(dp[i - 1][j 제외]) + land[i][j]
    */
    int length = land.size();
    for (int i = 1; i <= length; ++i)
    {
        for (int j = 0; j < MAX_COLUMN; ++j)
        {
            dp[i][j] = get_max_except(dp[i - 1], j) + land[i - 1][j];
        }
    }

    // dp배열의 마지막 행에서 최대값 반환
    return *max_element(dp[length], dp[length] + MAX_COLUMN);
}

 

TIP

복잡하게 생각하지 말고 DP로 풀면 간단하게 풀립니다 ㅜㅜ

열의 크기를 4로 주었다는 점(한정적, 작은 숫자)에서 DP문제의 힌트를 느낄수 있다.