백준 2169 (C++) 로봇 조종하기

최초 업로드: 2025-04-29 12:59:31

최근 수정 시간: 2025-07-25 08:53:33

게시자: rlatjwls3333

카테고리: 백준

# [Gold II] 로봇 조종하기

[문제 링크](https://www.acmicpc.net/problem/2169)

## 문제 설명

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

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

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

## 입력

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

## 출력

첫째 줄에 최대 가치의 합을 출력한다.

## 풀이
#### dp[i][j][0]을 (i, j)에서 왼쪽과 위쪽에서 온 경우의 최대 가치 합으로, dp[i][j][1]을 (i, j)에서 오른쪽과 위쪽에서 온 경우의 최대 가치 합으로 정해놓고 풀었다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int arr[1001][1002];
int dp[1001][1002][2]; // dp[i][j][k] : (i, j)에 (k=0 : 왼쪽에서 옴, k=1 : 오른쪽에서 옴) 인 경우의 최대 가치

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n, m; cin >> n >> m;
 for(int i=1;i<=n;i++) {
 for(int j=1;j<=m;j++) {
 cin >> arr[i][j];
 }
 }
 fill(&dp[0][0][0], &dp[1000][1001][2], -INF);

// 첫번째 줄
 dp[1][0][0]=0;
 for(int j=1;j<=m;j++) {
 dp[1][j][0] = dp[1][j-1][0] + arr[1][j];
 }

for(int i=2;i<=n;i++) {
 for(int j=1;j<=m;j++) {
 dp[i][j][0] = arr[i][j] + max({dp[i][j-1][0], dp[i-1][j][0], dp[i-1][j][1]});
 }
 for(int j=m;j>=1;j--) {
 dp[i][j][1] = arr[i][j] + max({dp[i][j+1][1], dp[i-1][j][0], dp[i-1][j][1]});
 }
 }
 cout << dp[n][m][0]; // (n, m)에는 왼쪽 또는 위쪽에서만 올 수 있음.
}
```