코드트리 신전 탐험하기

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

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

 

 

접근법 : dp유형문제이고

이전에 사용했던방은 또 들어가면안되는 문제입니다.

결국엔 점화식새워도 괜찮지만 재귀 + 메모이제이션이죠

 

 

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