[BaekJoon][2169] 로봇 조종하기

BAEKJOON ONLINE JUDGE

한국정보올림피아드 2002

2169 로봇 조종하기

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

왼쪽, 오른쪽, 아래로만 이동 -> 윗줄 까지는 최적

한 지점을 갈 때 왼쪽에서, 오른쪽에서, 위에서 가장 최대값 + 그 위치의 가치

이 때 이전 지점들은 예를들어 왼쪽에서 왔으면 그 지점은 그 왼쪽과 위만 경로롤 가질 수 있다 -> 중복탐색이 안되기 때문에

따라서 탐색할 때 한 줄을 위와 왼쪽에서 올 수 있는 값을 미리 저장, 오른쪽에서 올 수 있는 값을 따로 저장한 후 최종적으로 이 둘 중 Max값을 저장하면 최적의 값이 저장된다.

첫째 줄은 위와 오른쪽으로는 경로로 삼을 수 없다

계속 틀려서 1시간 30분 걸림

#include <stdio.h>
 
#define Max(x, y)        (((x) > (y))    ? (x) : (y))
 
int height, width;
int weight[1001][1001];
int map[1001][1001];
 
int solve()
{
    int i, j;
    int right[1001];
 
    for (i = 1; i <= width; i++)    map[1][i] = map[1][i - 1] + weight[1][i];
 
    for (i = 2; i <= height; i++) {
        map[i][1] = map[i - 1][1] + weight[i][1];
        for (j = 2; j <= width; j++) {
            map[i][j] = Max(map[i - 1][j], map[i][j - 1]) + weight[i][j];
        }
        right[width] = map[i - 1][width] + weight[i][width];
        for (j = width - 1; j > 0; j--) {
            right[j] = Max(map[i - 1][j], right[j + 1]) + weight[i][j];
        }
        for (j = 1; j <= width; j++) {
            map[i][j] = Max(map[i][j], right[j]);
        }
    }
 
    return map[height][width];
}
 
int main()
{
    int i, j;
 
    scanf("%d %d", &height, &width);
 
    for (i = 1; i <= height; i++)    {
        for (j = 1; j <= width; j++) {
            scanf("%d", &weight[i][j]);
        }
    }
 
    printf("%d\n", solve());
 
    return 0;
}