[프로그래머스 lv2] 땅따먹기 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

 

가장 먼저 떠오르는 풀이는 모든 경우의 수에 대해 점수를 구하고, 이 중 최댓값을 리턴하는 방법이다.

그러나 해당 방법의 시간 복잡도를 계산해보면, 4^100000 정도로 시간 초과가 100% 발생한다.

 

완전탐색 풀이는 시간초과가 발생할 때, 한번쯤 dp(동적프로그래밍) 방법을 떠올려보면 좋다.

dp[i][j]를 i번째 행, j번째 열에 도착할 떄까지의 최대 점수 라 정의하면,

 

dp[i][j] = max(dp[i-1][k]) + land[i][j] (단, k는 0, 1, 2, 3 중 j가 아닌 수) 

 

가 된다.

 

max(dp[i-1][k])는 i-1 번째 행을 밟을 때까지 점수의 최댓값이다.

동일한 열은 두 번 연속 밟을 수 없다고 했으므로, i행, j열의 땅을 밟기 위해서는 i-1번째 행을 밟을 때 j열이 아닌 땅을 밟아야 한다. 

따라서, 0부터 3까지를 순환하며 이번에 밟는 j번째 행을 제외하고 dp[i-1][k] 의 최댓값을 구한다.

 

이번 땅을 밟을 떄는 land[i][j] 만큼 점수를 얻을 수 있으므로, 이전 행까지의 최댓값에 land[i][j]를 더한다.

 

문제에서 요구한 값은 마지막 행까지 도달했을 때 점수의 최댓값이므로,

dp[N-1][0], dp[N-1][1], dp[N-1][2], dp[N-1][3] 중 최댓값을 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <cctype>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

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