[레벨 2] 땅따먹기

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<vector<int> > land)
{
    int answer = 0;
    int yLen = land.size(),y,x;
    
    for(y = 1; y < yLen; ++y)
    {
        land[y][0] += max({land[y - 1][1],land[y - 1][2],land[y - 1][3]});
        land[y][1] += max({land[y - 1][0],land[y - 1][2],land[y - 1][3]});
        land[y][2] += max({land[y - 1][0],land[y - 1][1],land[y - 1][3]});
        land[y][3] += max({land[y - 1][0],land[y - 1][1],land[y - 1][2]});
    }
    int max = -9999;
    for(x = 0; x < 4; ++x)
    {
        if(max < land[yLen - 1][x])
            max = land[yLen - 1][x];
    }
    
    return max;
}

많이 삽질을 하고 답을 봤던 문제. DP문제였다고 한다

 

처음에는 단순히 한 행의 최댓값을 찾고 다음행의 같은 열만 제외시키는 형태로 코드를 작성했지만 모두 실패.

 

여러 예외 케이스가 있었는데

4 3 2 1

2 2 2 1

6 6 6 4

8 7 6 5

와 같이 한 행의 최댓값이 여러개인데 처음 선택한 최댓값이 다른 최댓값보다 다음 행에 더한 값이 더 작게 나오는 예외.

이것을 처리해도 끝이 아닌게

 

1 2 3 5

5 6 7 100

4 3 2 1

과 같은 케이스. 첫행의 최댓값이 5이지만 바로 밑에 가장 큰 수 100을 무시해버림.

 

이러한 예외 케이스들을 없애주기위한 코드가 다음행에 최댓값을 더해주는것을 한번만 하지 않고.

최대값에 해당하는 같은열을 제외한 나머지 모두도 더해주는것.