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

< 해설 >

DP 문제! 어렵진 않다. 왜 for문을 돌면서 각 행의 최대값을 찾는 방식은 안되나요? 라는 의문점이 생길 수 있다. 이는 질문하기 란에 다른분이 들어준 예시를 보면 이해가 된다.

민윤기님 감사합니다!

 

이제 문제를 살펴보자. 열은 무조건 4개이다. (이걸 늦게봐서 살짝 헷갈림 ㅠㅠ)

그러므로 land[0], land[1], land[2], land[3] 만 있게 된다. 그렇다면

land의 1행의 인덱스 0번의 최대 누적값을 찾기 위해서는 land 0 행의 0번 인덱스를 제외한 1,2,3 인덱스의 최대값만 찾으면 된다!

방식은 Top-Down 방식이나 Bottom-Up 방식 둘중 아무거나 써도 된다. 난 for문 편하게 쓰려고 Top-Down 방식 썼다.

 

< 문제 >

 

< 풀이 >

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

int solution(vector<vector<int>> land)
{
    int answer = 0;    
    int maxIDX = -1;
    
    for(auto l : land)
    {
        l[0] += max( max(l[1], l[2]), l[3]);
        l[1] += max( max(l[0], l[2]), l[3]);
        l[2] += max( max(l[0], l[1]), l[3]);
        l[3] += max( max(l[0], l[1]), l[2]);
    }
    
    int size = land.size() - 1;
    int answer01 = max(land[size][0], land[size][1]);
    int answer02 = max(land[size][2], land[size][3]);
    
    return answer = max(answer01, answer02);
}