프로그래머스 - 땅따먹기

programmers.co.kr/learn/courses/30/lessons/12913

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

 

DP 를 이용해 푸는 문제이다.

1행 부터 시작해서 자기자신 보다 바로 윗행 중에서 동일한 열이 아닌 열을 선택하여

값을 더하면서 최대 값을 찾아 갱신하는 방식이다.

점화식으로 쓴다면 대략 이런 모습이 될것 같다

i >= 1, j = 0 일때 

dp[i][j] = max(dp[i][j] + dp[i - 1][j + 1], dp[i][j] + dp[i - 1][j + 2], dp[i][j] + dp[i - 1][j + 3])

 

i >= 1, j = 1 일때,

dp[i][j] = max(dp[i][j] + dp[i - 1][j - 1], dp[i][j] + dp[i - 1][j + 1], dp[i][j] + dp[i - 1][j + 2])

 

i >= 1, j = 2 일때,

dp[i][j] = max(dp[i][j] + dp[i - 1][j - 2], dp[i][j] + dp[i - 1][j - 1], dp[i][j] + dp[i - 1][j + 1])

 

i >= 1, j = 3 일때,

dp[i][j] = max(dp[i][j] + dp[i - 1][j - 3], dp[i][j] + dp[i - 1][j - 2], dp[i][j] + dp[i - 1][j - 1])

 

이걸 일일이 다 쓰기엔 너무 길고 부적합하므로

삼중 포문을 돌렸다

행의 최대 길이가 십만 이고, 열의 최대 길이가 4이므로 삼중 포문을 써도

10만 * 4 * 4 = 160만 이므로 시간 초과가 나지않는다.

 

 

- c++

처음엔 아래 같이 코드를 작성했으나 통과를 하기는 했다

근데 다시 생각해보면 굳이 불필요한 메모리를 추가로 할당하고 있었다. 

그래서 dp 배열을 없애고 land 배열 만으로 해결하려고 하였다. 

 

#include <algorithm>
#include <iostream>
#include <vector>
 
#define MAX 100001
 
using namespace std;
 
int dp[MAX][4];
 
int solution(vector<vector<int> > land) {
    int answer = 0, size = land.size();
    
    for (int i = 0; i < 4; ++i) dp[0][i] = land[0][i];
    
    for (int i = 1; i < size; ++i) {
        for (int j = 0; j < 4; ++j) {
            int num = 0;
            for (int k = 0; k < 4; ++k) {
                if (j != k) num = max(num, land[i][j] + dp[i - 1][k]);
            }
            dp[i][j] = num;
        }
    }
    
    for (int i = 0; i < 4; ++i) answer = max(answer, dp[size - 1][i]);
 
    return answer;
}

 

 

그래서 다음과 같이 더 코드를 줄였다

 

#include <algorithm>
#include <vector>
 
using namespace std;
 
int solution(vector<vector<int> > land) {
    int answer = 0, size = land.size();
        
    for (int i = 1; i < size; ++i) {
        for (int j = 0; j < 4; ++j) {
            int num = 0;
            for (int k = 0; k < 4; ++k) {
                if (j != k) num = max(num, land[i][j] + land[i - 1][k]);
            }
            land[i][j] = num;
        }
    }
    
    for (int i = 0; i < 4; ++i) answer = max(answer, land[size - 1][i]);
 
    return answer;
}

 

 

 

아무래도 백준에 익숙해지다보니, 전역변수로 선언하는게 더 습관화 된듯 하다.