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

 

DP문제인 것은 알았지만

바로 생각해내기에 어려운 문제..

우선 나는 그랬다.

 

 

 

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

 

---

이전 열에서의 최댓값을 채택하는 것이 현재열에서도 최댓값을 보장하는가?

이것에 대해 말할 수 있다면 풀 수 있다.

 

**다만 C++의 max는 2개의 비교만 되어서.. 하나씩 해줬다.

max_element는 iterator가 필요해서 그냥 나는 이걸로 했다.

 

# 맞는 풀이

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



int solution(vector<vector<int> > land)
{
    int answer = 0;
    
    //x열을 골랐을 때의 최댓값 = 이전 열에서 x를 제외하고 최댓값 + 현재 x열의 값.
    // -> 이전에 골랐던 값이 영향을 끼치는 것을 포착해서
    // 현재열을 업데이트함.
    
    //다시 말해서 이전 열에서의 최댓값을 가지는 열이 현재열의 선택에 영향을 미치지 않음.
    //이전 열에서 2번 열을 고르는 것이 이전 열을 최댓값으로 만들지라도
    //현재 열에서 2번열을 고르는 것이 최댓값을 만들 수 있음.
    //즉, 모든 열에 대한 선택을 업데이트해줘야함.
    
    //아래와 같이 모든 열에 대해서 업데이트
    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(max(land[land.size()-1][0],land[land.size()-1][1]),max(land[land.size()-1][2],land[land.size()-1][3]));


    return answer;
}