[BOJ]11048 - 이동하기 (C++)

문제

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

코드

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int dp[1001][1001];
int arr[1001][1001];

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

    int n, m; 
    cin >> n >> m; 

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

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            int rUp, cUp, rcUp; 

            cUp = dp[i-1][j];

            rUp = dp[i][j-1]; 

            rcUp = dp[i-1][j-1]; 

            dp[i][j] = arr[i][j] + max({cUp, rUp, rcUp});
        }
    }
    cout << dp[n][m];
}

풀이

준규는 (r+1, c), (r, c+1), (r+1, c+1) 중 최대로 이동해야 한다.
이 전에 계산 했던 결과를 dp[]에 담고 위의 3개의 좌표 중 최댓값으로 이동해서 dp의 값을 바꾼다.
for문이 i=1~n인 이유는 준규가 (1,1)에서 시작하기 때문이다.
아이디어를 생각해 내면 꽤 쉽게 풀 수 있는 문제였다.