[프로그래머스/C++]Lv.2 - 땅따먹기

문제 링크

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

시도한 방법

행마다 최댓값을 구하고 이전 행의 인덱스와 겹치면 -1로 바꾸고 다시 max를 구해서 더해갔다.
이러면 한 행에서 최댓값을 더했는데 다음 행에 같은 인덱스의 값이 엄청 크면 결국 최댓값을 얻지 못하게된다.

내 코드

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

int solution(vector<vector<int>> land)
{
    int answer = 0;
    int index = -1;
    
    for(vector<int> l : land)
    {
        auto iter = max_element(l.begin(),l.end());
        cout << index << endl;
        if(iter - l.begin() == index)
        {
            *iter = -1;
            iter = max_element(l.begin(),l.end());
            index = iter - l.begin();
            answer += *iter;
            continue;
        }
        answer += *iter;
        index = iter - l.begin();
    }
    
    return answer;
}

구글링 후

동적 계획법 ( Dynamic Programming ) 으로 풀이해야 한다는걸 찾았다.
( 동적 계획법에 대한 설명 )
https://ansohxxn.github.io/algorithm/dp/
이 문제에선 각 행에서 열마다 구할수 있는 가장 높은 값을 구해나가면서 그것을 더해나가는 방식으로 동적 계획법을 구현하였다.

코드

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

int solution(vector<vector<int>> land)
{
    int answer = 0;
    
    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][1],land[i-1][2]));
    }
    answer = *max_element(land.back().begin(), land.back().end());
    return answer;
}

풀이

i = 1 번째 행부터 각 열마다 이전 행에서 해당 index를 제외한 다른 index의 값 중 가장 큰 값을 더해나간다. 끝까지 더해나가면 마지막 행의 각 열마다 나올 수 있는 가장 큰 값들이 나오게 되고 거기서 가장 큰 값을 리턴해주면 된다.