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

문제

 

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

프로그래머스

 

 

문제풀이

 

같은 열을 연속으로 밟을 수 없다.

그리고 입출력 예를 보면 다음 행의 칸에서 같은 열만 아니면 다 밟을 수 있으므로 DP를 이용하면 쉽게 풀 수 있다.

 

이전 행에서 같은 열만 제외하고 남은 3칸 중에서 가장 큰 누적값과 현재 밟은 칸의 값을 더해 저장하면 된다.

DP[y][0] = ( DP[y-1][1] or DP[y-1][2] or DP[y-1][3] ) + land[y][0];

이 값을 4칸 모두 구한다.

 

반복문이 종료되면 마지막 행에서 가장 큰 값을 return 하면 끝난다.

 

코드

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

int get_max(int num1, int num2, int num3) {
    return max(num1, max(num2, num3));
}

int solution(vector<vector<int>>land)
{
    int answer(0);
    vector<vector<int>>DP(land.size(), vector<int>(4));

    for (int x = 0; x < 4; ++x) DP[0][x] = land[0][x];
    for (int y = 1; y < DP.size(); ++y) {
        DP[y][0] = get_max(DP[y - 1][1], DP[y - 1][2], DP[y - 1][3]) + land[y][0];
        DP[y][1] = get_max(DP[y - 1][0], DP[y - 1][2], DP[y - 1][3]) + land[y][1];
        DP[y][2] = get_max(DP[y - 1][0], DP[y - 1][1], DP[y - 1][3]) + land[y][2];
        DP[y][3] = get_max(DP[y - 1][0], DP[y - 1][1], DP[y - 1][2]) + land[y][3];
    }
    
    for (int x = 0; x < 4; ++x) {
        answer = max(answer, DP[DP.size() - 1][x]);
    }
    return answer;
}