[알고리즘 C++] 땅따먹기

https://programmers.co.kr/learn/courses/18/lessons/1880

dp인것을 아는순간 간단하다

오늘의 문제

땅따먹기

나의 풀이

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

int solution(vector<vector<int> > land)
{
    // dp
    int dp[100001][4];
    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++)
        {
            switch(j){
                case 0:
                    dp[i][j] = max(dp[i-1][1], max(dp[i-1][2], dp[i-1][3]))+land[i][j];
                break;
                case 1:
                    dp[i][j] = max(dp[i-1][0], max(dp[i-1][2], dp[i-1][3]))+land[i][j];
                break;
                case 2:
                    dp[i][j] = max(dp[i-1][0], max(dp[i-1][1], dp[i-1][3]))+land[i][j];
                break;
                case 3:
                    dp[i][j] = max(dp[i-1][0], max(dp[i-1][1], dp[i-1][2]))+land[i][j];
                break;
            }  
        }
    }
    int maxPoint =0;
    for(int i=0;i<4;i++)
    {
        maxPoint = max(maxPoint, dp[land.size()-1][i]);
    }

    return maxPoint;
}

모범 답안

#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]);
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < 4; ++i)
    {
        ans = max(ans, dp[r-1][i]);
    }
    return ans;
}

배울 점

• 나는 j의 case에 따라 max를 다르게 구하는 방법을 사용했는데, 코드가 지저분해 보이는 관계로 제외하는 방식을 쓰면 간단해질 것 같다
• C++로의 코딩테스트가 조금씩 적응이 되어가고 있다.