코드트리 신전 탐험하기 2

문제 URL : https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-explore-temple-2/description

신전 탐험하기 2 설명 | 코드트리

 

문제 접근법 : 신전 탐험하기 문제의 개선버전이군요

처음방에 들어갔던방은 마지막방에는 들어갈수 없는 조건이 붙여있기때문에 그만한 dp메모리를 더 사용해주면됩니다.

 

소스코드:

#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> v,dp[3];
int n;
int dfs(int f,int cur,int b){
    if(cur==n-1){
        return f==b?-1e9:v[cur][b];
    }
    int &cache = dp[f][cur][b];
    if(cache!=-1)return cache;
    int res = 0;
    res = max(dfs(f,cur+1,(b+1)%3),dfs(f,cur+1,(b+2)%3))+v[cur][b];
    return cache =res;
}
int main() {
    cin>>n;
    dp[0]=dp[1]=dp[2]= v = vector<vector<int>>(n,vector<int>(3,-1));
    for(int i =0;i<n;i++){
        cin>>v[i][0]>>v[i][1]>>v[i][2];    
    }
    cout<<max({dfs(0,0,0),dfs(1,0,1),dfs(2,0,2)});

}