Level 2. 땅따먹기

Level 2. 땅따먹기

 

 

재귀로 풀었더니 시간 초과가 발생했다.

 

// 이 풀이는 시간 초과가 발생한다.
#include <iostream>
#include <vector>
#include <set>

using namespace std;

void rSolution(int cur_col, int depth, int sum, vector<vector<int>>& land, set<int>& st)
{
    const static int row = land.size(), col = land.front().size();

    if (row <= depth)
    {
        st.emplace(sum);
        return;
    }

    for (int c = 0; c < col; ++c)
        if (c != cur_col)
            rSolution(c, depth + 1, sum + land[depth][c], land, st);
}

int solution(vector<vector<int>> land)
{
    set<int> st;

    rSolution(-1, 0, 0, land, st);

    return *st.rbegin();
}

 

DP 방식으로 n번째에서는 n-1번째까지의 합 중 최댓값을 더하고 n번째 중에서 최댓값을 구하면 된다.

 

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

using namespace std;

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

    for (int i = 1; i < n; ++i)
    {
        land[i][0] += max(land[i - 1][1], max(land[i - 1][2], land[i - 1][3]));
        land[i][1] += max(land[i - 1][0], max(land[i - 1][2], land[i - 1][3]));
        land[i][2] += max(land[i - 1][0], max(land[i - 1][1], land[i - 1][3]));
        land[i][3] += max(land[i - 1][0], max(land[i - 1][1], land[i - 1][2]));
    }

    return *max_element(land[n - 1].begin(), land[n - 1].end());
}