[백준 11048번] 이동하기

풀이

---

조건은 딱 세가지 경우이다.

1. 오른쪽으로 한칸

2. 아래로 한칸

3. 대각선 남동쪽으로 한칸

이 세가지 경우중 합이 가장 큰값을 찾아서 DP방식으로 풀어내면 가능하다.

재귀로 푸려고 했지만 2차원 배열에서 재귀로 풀면 시간초과가 나는 경우가 많아 DP로 시도했다.

소스코드

---

#include <iostream>
using namespace std;
 
int n, m, map[1001][1001];
int tmp_arr[2][1001];
 
int Max(int a, int b) {
    return a > b ? a : b;
}
 
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {  // i -> 세로
        for (int j = 0; j < m; j++) {  // j -> 가로
            cin >> map[i][j];
        }
    }
    for (int a = 0; a < n; a++) {
        // 복사
        for (int b = 0; b < m; b++) {
            tmp_arr[0][b] = map[a - 1][b]; // 이전칸
            tmp_arr[1][b] = map[a][b];  // 현재칸
        }
        //첫줄만 누적값
        if (a<1) {
            for (int b = 0; b < m; b++) {
                tmp_arr[0][b] += tmp_arr[0][b - 1];
            }
        }
        // 위랑 아래 비교
        tmp_arr[1][0] = tmp_arr[0][0] + tmp_arr[1][0]; // 첫번째칸은 위에꺼 + 현재칸
        for (int b = 1; b < m; b++) {
            int tmp = Max(tmp_arr[0][b]+tmp_arr[1][b], tmp_arr[1][b-1]+tmp_arr[1][b]);
            tmp_arr[1][b] = Max(tmp, tmp_arr[1][b] + tmp_arr[0][b - 1]);
        }
        // 대입
        for (int b = 0; b < m; b++) {
            map[a][b] = tmp_arr[1][b];
        }
    }
 
    cout << map[n - 1][m - 1] << '\n';
    return 0;
}