백준 16117 실버런 (C++)

https://www.acmicpc.net/problem/16117

16117번: 실버런

예제부터 이해하기 힘든 문제 였습니다. 예제2에서 많이 당황했어요. 혹시 못본게 있나 살펴봤더니 문제에

"정수 좌표가 아니어도 된다"라는 조건이 있더라고요. 그제서야 이해했습니다. .5지점에서 실버 주머니를 먹으면서 

이동할 수 있었습니다. 대신 .5지점에서 움직이게 될 경우 오른쪽으로 갈 경우 실버주머니를 먹지 못합니다. 이 경우를 주의하여 각각 정수좌표계에서 움직이는 dp .5좌표계에서 움직이는 dp로 나눠서 풀면 됩니다.

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
int N,M;
int arr[1200][1200];
int dp[1200][1200];
int dp2[1200][1200][2];
int main(){
    cin>>N>>M;
    for(int x=2;x<=N+1;x++){
        for(int y=2;y<=M+1;y++){
            cin>>arr[x][y];
        }
    }
    int ans=0;
    for(int x=2;x<=M+2;x++){
        for(int y=2;y<=N+1;y++){
            dp[y][x]=max(arr[y][x]+dp[y-1][x-1],arr[y][x]+dp[y+1][x-1]);
            dp[y][x]=max(dp[y][x],dp[y][x-2]+arr[y][x-1]+arr[y][x]);
            ans=max(dp[y][x],ans);
        }
    }
    for(int x=2;x<=M+2;x++){
        for(int y=2;y<=N+1;y++){
            for(int z=0;z<2;z++){
                if(z==0){
                    dp2[y][x][z]=max(dp2[y][x-1][1]+arr[y][x],dp2[y-1][x-1][0]+arr[y][x]);
                }
                if(z==1){
                    dp2[y][x][z]=max(dp2[y][x-1][0]+arr[y][x],dp2[y+1][x-1][1]+arr[y][x]);
                }
                ans=max(ans,dp2[y][x][z]);
            }
        }
    }
    cout<<ans;
}