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

문제 링크

땅따먹기

풀이

dp로 푸는 문제

1. 먼저 각 행과 열의 점수를 저장할 v를 초기화한다. v의 행과 열에는 그 행과 열을 밟을 경우의 최대 점수가 저장된다.
2. v의 맨 첫 행은 이 전에 밟은 것이 아니니 land값으로 초기화 하고,
   첫 행이 아니고, 그 열이 이 전의 열과 같지 않다면 (같은 열을 반복해서 밟으면 안되기 때문) 최대 점수를 저장하는데, 이 때 점화식은 v[i][j]=max(v[i][j], v[i-1][k]+land[i][j])
   2-1. 현재 저장된 점수와 갱신되는 점수를 비교해서 최대 값을 갱신해준다.
3. 마지막 행을 내림차순 정렬해주고 v[v.size()-1][0]을 출력한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

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

    vector<vector<int>> v(land.size(), vector<int>(4));
    for(int i=0;i<land.size();i++)
    {
        for(int j=0;j<4;j++)
        {
            if(i==0) // 맨 첫 행
            {
                v[0][j]=land[0][j];
            }
            else
            {
                for(int k=0;k<4;k++)
                {
                    if(k!=j)
                    {
                        v[i][j]=max(v[i][j], v[i-1][k]+land[i][j]);
                    }
                }
            }
        }
    }
    
    sort(v[v.size()-1].begin(), v[v.size()-1].end(), greater<int>());
    answer = v[v.size()-1][0];
    

    return answer;
}