[c++][백준 2169] 로봇 조종하기

백준 2169번: 로봇 조종하기
https://www.acmicpc.net/problem/2169

2169번: 로봇 조종하기

문제 풀이

• 이 문제는 DP(Dynamic Programming)로 구현했습니다. 

• 위의 그림에서처럼 한 칸을 계산하기 위해서는 3방향의 값을 고려해야 합니다. 3방향을 모두 고려하여 값을 계산하기 위해 다음과 같은 순서로 연산을 해줍니다.

• 첫 번째 줄을 계산하기 위해 1~2번의 연산을 하고, 2번째 줄부터 마지막 줄까지 3~5번의 연산을 해 줌으로 dp로 값을 구할 수 있습니다.

코드

#include <cstdio>
#include <algorithm>

using namespace std;

#define MAXN 1010

int arr[MAXN][MAXN];
int dp[MAXN][MAXN];
int temp[MAXN][2];

int n, m;

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[0][0] = arr[0][0]; // ---- 1
    for(int j=1; j<m; ++j) dp[0][j] = dp[0][j-1] + arr[0][j]; // ---- 2
    for(int i=1; i<n; ++i) {
        temp[0][0] = dp[i-1][0] + arr[i][0]; // ---- 3
        temp[m-1][1] = dp[i-1][m-1] + arr[i][m-1]; // ---- 3
		
        // ---- 4
        for(int j=1; j<m; ++j) temp[j][0] = max(dp[i-1][j], temp[j-1][0]) + arr[i][j];
        // ---- 5
        for(int j=m-2; j>=0; --j) temp[j][1] = max(dp[i-1][j], temp[j+1][1]) + arr[i][j];
        for(int j=0; j<m; ++j) dp[i][j] = max(temp[j][0], temp[j][1]);
    }

    printf("%d", dp[n-1][m-1]);

    return 0;
}

실행 결과