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

https://school.programmers.co.kr/learn/courses/30/lessons/12913

프로그래머스

풀이

2차원 벡터 land가 주어졌을 때, 각 열의 값 중 하나를 선택하면서 더하고, 행의 마지막에 도달했을 때 최종합의 최대값을 구하는 문제입니다. 단, 연속으로 같은 열의 값을 선택할 수 없습니다.

 

N 의 최대값이 100,000 이므로 brute-force가 불가능할 뿐더러, 연속으로 같은 열의 값을 선택할 수 없으므로 greedy 한 선택 또한 할 수 없습니다.

예시로,

1, 2, 3, 4

1, 2, 4, 100

일 때, 첫번째 행에서 4를 선택했을 경우 최종해는 8입니다. 하지만 3을 선택했을 경우 103이라는 최종해가 나옵니다.

따라서, dp를 사용해 완전탐색을 진행해줍니다.

 

각 land[i][j] 에서 가질 수 있는 최대값은 land[i-1][j]를 제외한 값 중 최대값과 더하는 것입니다. 이를 수식으로 나타내면,

land[i+1][0] += max(land[i][1], max(land[i][2], land[i][3])) 입니다. 나머지 1, 2, 3열에 대해서도 동일한 방식으로 계산해줍니다.

 

최종적으로, 마지막 행에서의 최대값이 땅따먹기를 진행할 때 가질 수 있는 최종해입니다.

해당 값은 max_element 함수를 사용해 구할 수 있습니다. 

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

using namespace std;

// land : N행 4열, 같은 열을 연속해서 밟을 수 없다
// dp : 각 land[i][j]에서 가질 수 있는 최대값 기록
 

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