BOJ : 2169 로봇

문제 : https://www.acmicpc.net/problem/2169

출처

Olympiad > 한국정보올림피아드 > KOI 2002 > 고등부 1번

N, M의 최대가 1000이므로 완전탐색으로는 무리가 있을 수 있다.

또한 좌, 우, 아래의 이동을 잘 해결해주어야한다.

나는 재귀로 해결쓰. DP[][][0]은 아래 [1]은 우측, [2]는 좌측을 나타낸다.

제일 처음 1,1에서 출발하여 N,M까지 갈 수 있는 모든 경로를 간다.

그리고 리턴을 하면서 기준 노드의 좌,우,하에서 리턴되는 값들을 비교해서 큰 값만 저장하게 되면 마지막 1,1에 남는 값이 최대값이 된다.

#include <iostream>
#define INF -9876543210
long long dp[1002][1002][3];
int map[1002][1002];
bool visited[1002][1002];
int N,M;
long long DP(int r, int c, int d){
    if(r==N && c==M) return map[r][c];
    long long v1=INF,v2=INF,v3=INF;
    long long &ret = dp[r][c][d];
    if(ret != INF) return ret;
    visited[r][c]=1;
    if(r+1 <= N && !visited[r+1][c]) v1= DP(r+1, c,0);
    if(c+1 <= M && !visited[r][c+1]) v2 = DP(r, c+1,1);
    if(c-1 > 0 && !visited[r][c-1]) v3=DP(r,c-1,2);
    ret = std::max(std::max(v1,v2),v3)+map[r][c];
    visited[r][c]=0;
    return ret;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++){
            scanf("%d",&map[i][j]);
            dp[i][j][0]=dp[i][j][1]=dp[i][j][2]=INF;
        }
    printf("%lld\n",DP(1,1,0));
}