[알고리즘] DP 기본 ③

문제 출처 : 프로그래머스 땅따먹기 lv2.

1. 문제 풀이

1) 입출력 예시

2) 문제 풀이

• 1행(5) -> 2행(7) -> 3행(4) = 16점 획득

① N행X4열로 구성된 맵의 1행부터 N행까지 이동
② 각 행마다 한 개의 열만 지날 수 있음
③ 같은 열은 연속해서 밟을 수 없음
④ N행을 모두 탐색 후 최고점을 return

2. Solution I.

1) solution1.cpp

각 행을 지날 때마다 i행j열의 최댓값을 계산

[3x4]
1 2 3 5
5 6 7 8
4 3 2 1

[3x4 최댓값 계산]
1 2 3 5
10 11 12 11
16 15 13 13

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

// N행 4열
int solution(vector<vector<int> > land)
{
    int answer = 0;
    int n=land.size();
    cout<<n<<endl;
    vector<vector<int>> mp(n, vector<int>(4, 0)); 
    
    for(int x=0;x<4;x++)
        mp[0][x]=land[0][x];
    
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<4;j++)
        {
            // i행 j열
            int max=0;
            for(int k=0;k<4;k++)
            {
                if(k!=j && max<mp[i-1][k])
                    max=mp[i-1][k];
            }
            mp[i][j]=max+land[i][j];
        }
    }
    
    for(int x=0;x<4;x++)
        if(answer<mp[n-1][x])
            answer = mp[n-1][x];

    return answer;
}