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

• 문제
  • 마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요.

• 설명
  • 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다.
  • 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 
  • 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

• 풀이
  • DP로 해결했다.
  • dp[i][0] += max(dp[i-1][3], max(dp[i-1][1], dp[i-1][2]) )
  • i 행에 n열의 값은 i-1 행에서 n이 아닌 열 중의 최댓값 + 자신의 값
  • 마지막 행 중의 최댓값이 답이 된다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int solution(vector<vector<int> > land)
{
    int answer = 0;
 
    //한 행씩 내려올때 같은 열을 밟을 수 없음.
    //최고점을 반환
    
    //dp로 해결
    int end = land.size()-1;
    for(int i = 1 ; i < land.size() ; 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][2],land[i-1][1]));            
    }
    
    answer = max(land[end][0],max(land[end][1],max(land[end][2],land[end][3])));
 
    return answer;
}