(프로그래머스 c++)땅따먹기

DP를 이용하여 문제를 풀었다..!

 

우선 열의 개수는 무조건 4개이다. 시간은 충분할 것 같다..!

3중 for문을 이용하도록 하자.

 

i = 1부터 시작하여, i - 1 행의 수를 모두 비교해야 한다.

단, j != k여야 같은 열 번호의 수를 선택하지 않는다.

m은 현재 행의 위치에서 이전 행의 각 열을 더했을 때 가장 큰 값을 저장하는 변수이다.

그리고 이전의 최댓값이 누적이 되므로 마지막 행에서 최댓값만 찾으면 된다..!

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

using namespace std;

int solution(vector<vector<int> > land)
{
    int answer = 0, m = 0;
    
    for(int i = 1; i < land.size(); i++)
    {
        for(int j = 0; j < 4; j++)
        {
            m = 0;
            for(int k = 0; k < 4; k++)
            {
                if(j != k)
                    m = max(m, land[i - 1][k]);
            }
            land[i][j] += m;
        }
    }
    
    for(int i = 0; i < 4; i++)
        answer = max(answer, land[land.size() - 1][i]);
    return answer;
}