백준 - 9465 스티커

[문제 링크]

DP문제이다. 어려운 문제는 아니고, 다음으로 선택할 수 있는 경로의 경우만 알면 쉽게 풀리는 문제인 것 같다.

자신을 기준으로 상하좌우는 접근할 수 없기 때문에, 대각선에 위치한 스티커나, 대각선에서 오른쪽으로 한칸 옆에 있는 스티커를 다음 경로로 선택하면 된다.

이렇게 모든 점수들을 더한 값 중 최대값을 구하면 되었다.

밑은 이를 구현한 코드이다.

#include <cstdio>
#include <cstring>
#include <algorithm>
int t,n,arr[2][100000],cache[2][100000];
int relPos[4][2] = {{1,1},{1,-1},{2,-1},{2,1}};
int dp(int y, int x){
    //기저사례 : y 끝에 도달했을 때 
    if(x==n-1) return arr[y][x];
    int& ret = cache[y][x];
    if(ret!=-1) return ret;
    ret = 0;    
    for(int i=0;i<4;i++){
        int px = x + relPos[i][0];
        int py = y + relPos[i][1];
        //스티커 범위를 초과하지 않으면 
        if(px<n&&px>=0&&py<2&&py>=0){
            //최대값 구하기, 기존 ret와, 이 값+ 현재 좌표값 
            ret = std::max(ret,dp(py,px)+arr[y][x]);
        }
    }
    return ret;
}
int main(){
    scanf("%d",&t);
    while(t--){
        memset(cache,-1,sizeof(cache));
        scanf("%d",&n);
        for(int y=0;y<2;y++){
            for(int x=0;x<n;x++){
                scanf("%d",&arr[y][x]);
            }
        }
        //(0,0)으로 시작할 때랑, (1,0)으로 시작할때 중 최댓값을 구하여 출력한다.              
        printf("%d\n",std::max(dp(0,0),dp(1,0)));
    
    }   
}