[BOJ 백준] 2169번 로봇 조종하기

문제

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

2169번: 로봇 조종하기

접근

탐사 로봇은 (1, 1)의 위치부터 (n, m)까지 탐사하는 방법 중 탐사한 지역들의 가치의 합이 최대인 값을 찾는 문제이다.

나는 dp로 접근했다. 먼저 임의의 좌표에 도달하기 위해서는 그 좌표의 위 또는 왼쪽 또는 오른쪽에서 접근할 수 있다. 

따라서 왼쪽에서 오는 최댓값과 위에서 오는 최댓값을 비교해 최댓값을 저장해주는 배열 left_max와 오른쪽에서 오는 최댓값과 위에서 오는 최댓값을 비교해 최댓값을 저장해주는 배열 right_max를 만들어 주었다.
한 행의 left_max와 right_max를 구했다면 다음 행으로 가기 전에 둘 중 최댓값을 구해 배열에 저장해 준다.
이런 식으로 진행하다 보면 dp의 특성상 마지막 좌표는 우리가 원하는 대로 최댓값을 가지고 있을 것이다.
코드가 매우 직관적이니 참고하면 이해하는 데 도움이 될 것이다.

코드

// algorithm study
// BOJ_2169_로봇 조종하기

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    int map[1010][1010];
    int left_max[1010][1010];
    int right_max[1010][1010];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }

    for (int i = 0; i < n; i++) {
        //left_max
        for (int j = 0; j < m; j++) {
            if (i == 0) {
                if (j == 0)
                    left_max[i][j] = map[i][j];
                else
                    left_max[i][j] = map[i][j] + left_max[i][j - 1];
            } else {
                if (j == 0)
                    left_max[i][j] = map[i][j] + map[i - 1][j];
                else {
                    int a = left_max[i][j - 1] + map[i][j];
                    int b = map[i - 1][j] + map[i][j];
                    if (a > b)
                        left_max[i][j] = a;
                    else
                        left_max[i][j] = b;
                }
            }
        }
        //right_max
        for (int j = m - 1; j >= 0; j--) {
            if (i == 0) {
                right_max[i][j] = left_max[i][j];
            } else {
                if (j == m - 1)
                    right_max[i][j] = map[i][j] + map[i - 1][j];
                else {
                    int a = right_max[i][j + 1] + map[i][j];
                    int b = map[i - 1][j] + map[i][j];
                    if (a > b)
                        right_max[i][j] = a;
                    else
                        right_max[i][j] = b;
                }
            }
        }

        for (int j = 0; j < m; j++) {
            if (left_max[i][j] > right_max[i][j])
                map[i][j] = left_max[i][j];
            else
                map[i][j] = right_max[i][j];
        }
    }

    cout << map[n - 1][m - 1];

    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study