(C++) - 프로그래머스(연습문제) : 땅따먹기

programmers.co.kr/learn/courses/30/lessons/12913?language=cpp

코딩테스트 연습 - 땅따먹기

bottom dp문제였습니다.

 

 

풀이방법

 i+1의 j번째 열을 선택할 때의 점수 = max(i번째 행의 j번째열을 제외한 나머지 열들의 점수들 중 최대) + 현재 i+1,j의 발판 점수

 

land.size()-1번째 행의 모든 열들 중 최대가 최종 점수입니다.

 

Code

#include <bits/stdc++.h>
using namespace std;

int solution(vector<vector<int> > land){
    int answer = 0;
    int d[100001][4];
    memset(d,0,sizeof(d));
    for(int i = 0; i < 4; i++)
        d[0][i] = land[0][i];
    
    for(int i = 0; i < land.size() - 1; i++){
        d[i+1][0] += max({d[i][1],d[i][2],d[i][3]}) + land[i+1][0];
        d[i+1][1] += max({d[i][0],d[i][2],d[i][3]}) + land[i+1][1];
        d[i+1][2] += max({d[i][0],d[i][1],d[i][3]}) + land[i+1][2];
        d[i+1][3] += max({d[i][0],d[i][1],d[i][2]}) + land[i+1][3];
    }

    for(int i = 0; i < 4; i++)
        answer = max(answer,d[land.size()-1][i]);
    return answer;
}