Programmers 12913 땅따먹기

26 Mar 2021 in Algorithm

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12913

나의 풀이

DP[i][j] = i행 j열에서 얻을 수 있는 점수의 최대값

DP[i][0] = land[i][0] max(DP[i-1][1], DP[i-1][2], DP[i-1][3])
DP[i][1] = land[i][1] max(DP[i-1][0], DP[i-1][2], DP[i-1][3])
DP[i][2] = land[i][2] max(DP[i-1][0], DP[i-1][1], DP[i-1][3])
DP[i][3] = land[i][3] max(DP[i-1][0], DP[i-1][1], DP[i-1][2])

풀이 코드 : 12913 땅따먹기

#include <iostream>
#include <vector>

using namespace std;

int DP[100000][4];

int solution(vector<vector<int> > land)
{
    int answer = 0;
    for(int i=0;i<4;i++) DP[0][i] = land[0][i];
    for(int i=1;i<land.size();i++){
        for(int j=0;j<4;j++){
            int max = -1;
            for(int k=0;k<4;k++){
                if(j==k) continue;
                if(max < DP[i-1][k]) max = DP[i-1][k]; 
            }
            DP[i][j] = max + land[i][j];
        }
    }
    for(int i=0;i<4;i++){
        if(answer < DP[land.size()-1][i])
            answer = DP[land.size()-1][i];
    }
    return answer;
}

채점결과