땅따먹기

들어가는 말

2월달에 토익 공부한다고 코딩 테스트에 신경을 못 썼다. 조금 놀기도 했고... ㅎㅎ. 3월도 됐고 휴학도 했으니, 취업 준비 겸 이것저것 하면서 다시 시작할 생각이다.

벡터가 주어지는 데, 한 행에서 숫자를 고르면 다음 행의 같은 열은 못 고르는 방식으로 숫자를 선택한다. 그리하여 최댓값을 구하는 것이다.
처음에는 각 행에서 최댓값을 찾아 전부 더해주면 된다고 생각했다. 그러나, 테스트 1은 통과했으나 제출에서는 전부 틀리는 게 아닌가. 찾아보니까, 그렇게 구하면 전체의 최댓값을 구하기 어렵다는 걸 알아냈다. 한 행에서의 최댓값을 구해주는 게 아니라 모든 경우의 수를 구해 최댓값을 구해주는 동적계획(DP) 방식으로 풀어야 했다.

코드 설명

열은 4로 정해져 있지만 행은 정해져 있지 않으므로 반복문은 행만 기준으로 돌려주면 된다. 각 행의 열마다 최댓값을 구해주는데 i+1에다가 구해진 값을 더해주면 된다. 그렇게 되면 i+1의 행들은 최댓값이 된다. 그렇게 반복해 준 다음에 마지막 열(마지막 열에 전체 결과가 나와있으니까) 총 4개의 행 중에서 최댓값을 찾으면 된다.
여기서 주의할 점은 i+1에 더할 때 같은 열은 더해줘서는 안 된다는 점이다.

코드

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

int solution(vector<vector<int> > land)
{
    int answer = 0;
    
    for(int i=0; i<land.size()-1; i++){
        land[i+1][0] = land[i+1][0] + max(land[i][1], max(land[i][2], land[i][3]));
        land[i+1][1] = land[i+1][1] + max(land[i][0], max(land[i][2], land[i][3]));
        land[i+1][2] = land[i+1][2] + max(land[i][0], max(land[i][1], land[i][3]));
        land[i+1][3] = land[i+1][3] + max(land[i][0], max(land[i][1], land[i][2]));
    }
    
    answer = max(land[land.size()-1][0], max(land[land.size()-1][1], max(land[land.size()-1][2], land[land.size()-1][3] )));

    return answer;
}