[프로그래머스][dp] 땅따먹기

프로그래머스 알고리즘 강좌가 dp 이해에 도움이 됐다는 글을 보고 '땅따먹기'를 시도했다. 직접 짜보고 dp 코드와 비교하니까 dp의 느낌이 확 와닿는다. dp는 모든 경우의 수를 확인하는데, 각 요소가 있고, 없고에 따라 경우를 만든다. 

문제와 함께 보자

 

문제

ㅎ. 하지만 나는 어제 dp를 정리해 놓고도 전혀 떠오르지 않아서 풀리는 대로 풀었다. (이해가 덜 됐다ㅜ)

내 풀이 방법

1. 현재 index(j)를 이전 max의 index와 비교해 같지 않은 경우에만 들어간다. 
  - if ( i == 0 ) 인 예외를 주는 데 시간이 오래 걸렸다. 다시 생각해 보니 첫 열은 index가 뭐든 관계없으니까 preindex 처음 선언할 때 preindex = -1; 했으면 됐겠다. 

2. index가 같지 않은 경우에만 max의 값을 업데이트할 기회를 준다.

3. max 값은 answer에 바로 저장하고 검사용 preindex를 업데이트한다.

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

int main() {
    vector<vector<int>> land = {
        {1, 2, 3, 5},
        {5, 6, 7, 8},
        {4, 3, 2, 1}
    };

    int answer = 0, preindex, index, max;

    for (int i = 0; i < land.size(); i++) {
        max = 0, index = 0, preindex = 0;
        for (int j = 0; j < 4; j++) {
            if (i==0 or j != preindex) {
                if (max < land[i][j]) {
                    max = land[i][j];
                    index = j;
                }
            }
        }
        answer += max;
        preindex = index;
    }

    return answer;

}

 

테스트 코드만 통과했다. 게다가 비효율적이다. 만약에 land [ 3 ][ j ] 값을 이용한다 치면 이미 했던 계산을 또 해야 하기 때문이다. 

해설은 dp를 이용했다. 이제 약간 감이 잡혔다.  dp의 memoization은 갔던 모든 경로를 이전에 구한 값을 이용해 만드는 배열이다. 

 

해설 코드

#include<vector>
using namespace std;

int dp[100001][4] = {0};
int solution(vector <vector<int> > land) {
    int r = land.size();
    for (int i = 0; i < 4; ++i) {
        dp[0][i] = land[0][i];
    }

    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < 4; ++j) {
            for(int k = 0; k < 4; ++k) {
                if (j != k) {
                    dp[i][j] = max(dp[i][j], land[i][j] + dp[i-1][k]);
                    //dp에 넣을 값은 현재 land를 넣지 않는 경우와 넣는 경우(0, 1)를 말한다.
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < 4; ++i) {
        ans = max(ans, dp[r-1][i]);
    }
    return ans;
}

 

위에서부터 아래로 내려가는 방법 ↓ 이랑 아래에서 위로 올라가는 코드 ↑ 가 있고, 아래에서 위로 올라가는 코드도 익숙해져야한다고 했다. 각각 하향식(Memoization)와 상향식 풀이(Tabulation) 를 의미한다. 상향식 풀이의 예는 피보나치에서 f[0] = 0, f[1] = 1 이렇게 요소의 값을 넣어놓고 이를 조합해 f[n]을 구하는 방식을 의미한다. 

 

<어려워>
오늘 계절 미적분학 교수님께서 대학 공부는 원칙대로 차근차근 이해하는 게 아니라 일단 한 번 훑고 나중에 다시 보고 이해하는 거라고 하셨다. 아몰랑 나는 그렇게 해야겠다 (눈귀막귀)

 

< DP 배낭의 응용이므로 배낭을 이해하기 좋은 영상을 첨부했다. >

https://youtu.be/rhda6lR5kyQ?si=LmfgjoV-pNC0u3Sf