코드트리 신전 탐험하기 3

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

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

 

문제 접근법 신전탐험하기 1 문제랑 다를게없고 이번에 m개의 방이있다고하니

그냥 메모리를 n*m 을 써주면 되는문제라 크게 설명드릴건없을것같아요

 

소스코드:

 

 

 

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

 

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.