[C++/BOJ] 2169 : 로봇 조종하기 (DP)

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

문제

NASA에서는 화성 탐사를 위해 화성에 무선 조종 로봇을 보냈다. 실제 화성의 모습은 굉장히 복잡하지만, 로봇의 메모리가 얼마 안 되기 때문에 지형을 N×M 배열로 단순화 하여 생각하기로 한다.

지형의 고저차의 특성상, 로봇은 움직일 때 배열에서 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만, 위쪽으로는 이동할 수 없다. 또한 한 번 탐사한 지역(배열에서 하나의 칸)은 탐사하지 않기로 한다.

각각의 지역은 탐사 가치가 있는데, 로봇을 배열의 왼쪽 위 (1, 1)에서 출발시켜 오른쪽 아래 (N, M)으로 보내려고 한다. 이때, 위의 조건을 만족하면서, 탐사한 지역들의 가치의 합이 최대가 되도록 하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다.

---

백준 골드2 dp문제!

자칫하면 그래프 탐색 문제로 오해할 수 있을 것 같았다.

그리고 60퍼센트 정도에서 틀린다면 아래처럼 전체가 음수인 테스트케이스를 고려해볼 것!

제가 그렇게 틀렸어요,,,

 

반복문 돌리면서 dp를 채울 때, 범위를 잘 설정해야 한다.

이차원배열을 출력하면서 코드를 수정하면 도움이 된다^-^

 

으아아

나의 풀이

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int n;
int m;
int map[1001][1001];
int fromRight[1001];
int fromLeft[1001];
int dp[1001][1001];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

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

    for (int j = 1; j <= m; ++j)
    { // 맨 윗줄
        dp[1][j] += dp[1][j - 1] + map[1][j];
    }

    for (int i = 2; i <= n; ++i){
        // 왼 vs 위
        fromLeft[1] = dp[i - 1][1] + map[i][1];
        fromRight[m] = dp[i - 1][m] + map[i][m];
        for (int j = 2; j <= m; ++j){
            fromLeft[j] = max(dp[i - 1][j], fromLeft[j - 1]) + map[i][j];
        }
        // 오 vs 위
        for (int j = m-1; j > 0; --j){
            fromRight[j] = max(dp[i - 1][j], fromRight[j + 1])+ map[i][j];
        }
        // max를 dp에 저장
        for (int j = 1; j <= m; ++j){
            dp[i][j] = max(fromLeft[j], fromRight[j]);
        }
    }
    
    // cout << "\n";
    // for (int i = 0; i <= n+1; ++i){
    //     for (int j = 0; j <= m+1; ++j){
    //         cout << dp[i][j] << " ";
    //     }
    //     cout << "\n";
    // }

    cout << dp[n][m];
}