백준_11048_이동하기

🙋‍♀️ 문제

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

11048번: 이동하기

 

🧩 알고리즘

다이나믹 프로그래밍 (DP)

 

💡 아이디어

D[i][j] = (1, 1)에서 시작해서 (i, j)에 도착했을 때 사탕 개수의 최댓값.

 

(i, j)에 도착했을 때 가능한 경우의 수 (D[i][j]를 만들 수 있는 방법 3가지):

case 1) (1, 1) → (i, j - 1) → (i, j) 이때, D[i][j] = D[i][j - 1] + A[i][j]

case 2) (1, 1) → (i - 1, j) → (i, j) 이때, D[i][j] = D[i - 1][j] + A[i][j]

case 3) (1, 1) → (i - 1, j - 1) → (i, j) 이때, D[i][j] = D[i - 1][j - 1] + A[i][j]

→ D[i][j] = max(case 1, case 2, case 3) + A[i][j]

 

하지만, 대각선 이동은 오른쪽→아래 / 아래→오른쪽 두 방법보다 항상 사탕 개수가 적거나 같으므로 고려하지 않아도 됨 (A[i][j] ≥ 0 일 때만). 따라서, case 3 은 제거 가능.

 

👩‍💻 코드

#include <iostream>
#include <algorithm>

using namespace std;

int a[1001][1001];
int d[1001][1001];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // input
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    // dp
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            d[i][j] = max(d[i - 1][j], d[i][j - 1]) + a[i][j];
        }
    }
    // output
    cout << d[n][m] << '\n';
    return 0;
}