[ 프로그래머스 ] 땅따먹기

문제

---

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

풀이

---

경로에 따른 최댓값을 찾는 문제로, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 존재한다. 따라서 메모이제이션을 통해 지난 행과 같은 행의 땅을 밟지 않으면서 가질 수 있는 최댓값을 저장하여 경로에 따른 최댓값을 찾는다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>

using namespace std;

int row;
int lands[100000][4];

//Memoization recursion
int findMax(int row_pos, int col_pos, vector<vector<int>>& land)
{

    if (row_pos == row - 1)
    {
        return land[row_pos][col_pos];
    }

    int& ret = lands[row_pos][col_pos];
    if (ret != -1)
    {
        return ret;
    }

    int temp = 0;
    for (int i = 0; i < 4; i++)
    {
        if (i == col_pos) continue;
           
        temp = max(temp, findMax(row_pos + 1, i, land));
    }

    return lands[row_pos][col_pos] = land[row_pos][col_pos] + temp;
}


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

    memset(lands, -1, sizeof(lands));

    for (int i = 0; i < 4; i++)
    {
        answer = max(answer, findMax(0, i, land));
    }

    return answer;
}