[프로그래머스 / Level_2 / C++] 땅따먹기

이차원 dp를 활용해서 푼 문제이다. 

 

#접근방법 

 

해당 문제는 Top-down 방식으로 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식을 썼다. 

 

먼저 현재 위치한 인덱스 번호를 pos에 저장을 하였고 다음 재귀호출을 할 때는 현재 pos에 저장된 열의 번호가 아닌 다른 3개의 열을 나타내는 값으로 전달한다.

 

언제까지 호출하냐? 

 

2차원 배열 사이즈가 같을 때까지 계속 호출한다. 즉, Level 이 행의 크기만큼 왔을 때는 더 이상 호출할 수 없기 때문에 이때부터 리턴값을 전달해준다. 

 

리턴한 값들은 이전에 재귀함수를 호출했던 코드영역에 가서 반환 받은 값들의 크기를 비교해서 큰 값을 

dp에 저장한다. 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int level; 
vector<vector<int>> dp; 
vector<vector<int>> v; 
int dfs(int l, int pos){
    if(l==level) return 0; 
    int &res = dp[l][pos]; 
    if(res)return res; 
    res = 0; 
    for(int i=0; i<4; i++){
        if(pos==i){
            continue; 
        }
        else{
            res = max(res, v[l][pos] + dfs(l+1, i)); 
        }
    }
    return res; 
}

int solution(vector<vector<int> > land)
{
    level = land.size(); 
    v = land; 
    dp.resize(land.size(), vector<int>(4,0));
    int answer =0; 
    for(int i=0; i<4; i++){
       answer= max(answer, dfs(0, i)); 
    }
    return answer;
}

 

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