📒활용 개념

DP(Dynamic Programming)와 Memoization을 활용하여 시간복잡도를 감소시켰다.

📌문제설명

N행 4열로 이루어져있는 땅에서 각 행 중 한칸만 밟으며 내려온다. 단 한 행씩 내려오며 같은 열을 연속해서 밟을 수 없다. 마지막 행 까지 내려왔을 때 점수의 최대값을 구하라.
예를 들면,

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |
1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 된다.

📌구현

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

int solution(vector<vector<int> > land)
{
    int answer = 0;

    for(int i=land.size()-1; i>0; i--){
    //i-1으로 가장 아래의 바로 윗 칸 부터 i의 값을 줄이며 아래에서 위로 문제를 해결한다.
        land[i-1][0]+=max(land[i][1], max(land[i][2], land[i][3]));
        land[i-1][1]+=max(land[i][0], max(land[i][2], land[i][3]));
        land[i-1][2]+=max(land[i][1], max(land[i][0], land[i][3]));
        land[i-1][3]+=max(land[i][1], max(land[i][2], land[i][0]));
    }
    
    //가장 윗 행에서 최종 결과값을 얻고 가장 위의 행 중 가장 큰 열을 찾는다.
    answer=max(max(land[0][0], land[0][1]), max(land[0][2], land[0][3]));
   
    return answer;
}

가장 아래의 바로 윗 행 부터 자신이 가질 수 있는 가장 큰 값을 구해주며 진행했다.

📌주의점

• 처음에는 그저 DFS를 이용하여 모든 경우의 수를 확인하려 했으니 Runtimeerror이 일어났다.
• 모든 경우의 수를 확인하는 것 보다, DP를 활용하여 기존의 계산을 기억하고 다시 하지 않는 것이 더 효율적이었다.
• DP를 활용해야 하는 문제에 대해 바로 알 수 있도록 해야한다.