문제

이 문제는 최대 경로 찾기 같아 보인다. 일단 사이클이 존재하지 않는다는 점에서 디피를 쓸 수 있어보였다.

문제 링크

문제 접근

  • 로봇은 위로 이동할 수 없고 같은 지역은 또 방문할 수 없다. 때문에 각 위치의 최대 값을 담고 있는 어레이 dp를 준비해주고 위에서 부터 각 위치 값을 업데이트 해나가면 된다.
  • 예제에서 2번째 줄의 첫번째 값은 1번째 줄 첫번째 값에서 바로 내려오거나, 2번째, 3번째, 4번째, 5번째 값에서 내려와서 값들을 더하면서 만들 수 있는 값 중에 제일 큰 애를 저장하면 된다.
  • 이 과정을 단순화 하기 위해, 이전 줄에서 내려와서 왼쪽으로 가는 경우, 오른쪽으로 가는 경우 두 경우를 이용해 현재 줄의 값을 최신화 하였다.

코드

#include <cstdio>
int n, m, arr[1001][1001], dp[1001][1001];

int main(){
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            scanf("%d", &arr[i][j]);
            dp[i][j] = -987654321;
        }
    }
    dp[0][0] = arr[0][0];
    for(int i = 1; i < m; i++)dp[0][i] = dp[0][i - 1] + arr[0][i];
    for(int i = 1; i < n; i++){
        for(int j = 0; j < m; j++){
            int sum = dp[i - 1][j];
            for(int k = j; k < m; k++){
                sum += arr[i][k];
                if(dp[i][k] < sum)dp[i][k] = sum;
            }
            sum = dp[i - 1][j];
            for(int k = j; k >= 0; k--){
                sum += arr[i][k];
                if(dp[i][k] < sum)dp[i][k] = sum;
            }
        }
    }
    printf("%d", dp[n - 1][m - 1]);
}

느낀점

  • 디피랑 친해지고 있는 듯하다(?)