백준 11048 / 이동하기

다이나믹 프로그래밍 문제

가중치는 같지만 사탕을 가져올 수 있는 최대값을 문제이기 때문에 BFS로 풀 수 없다.

다양한 점화식이 있지만 가장 간단한 방법을 사용했다.

D[i][j]가 i,j에 도착했을때 가진 사탕의 최대값, map[i][j]가 i,j에 놓인 사탕의 개수라 가정했을 때,

위에서 왔을 경우 : D[i][j] = D[i-1][j] + map[i][j]

왼쪽에서 왔을 경우 : D[i][j] = D[i][j-1] + map[i][j]

왼쪽 위 대각선에서 왔을 경우 :  D[i][j] = D[i-1][j-1] + map[i][j]

이기 떄문에

D[i][j]는 max(D[i-1][j], D[i][j-1], D[i-1][j-1]) + map[i][j]이 된다.

문제의 조건인 (1,1)에서 시작하여 (n,m)으로 도착하는 문제이기 떄문에

i-1이나 j-1의 범위 검사를 해주지 않아도 된다 (map이 0으로 초기화 되었기 떄문)

코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
 
using namespace std;
 
int map[1001][1001];
int d[1001][1001];
 
int main() {
    freopen("Text.txt", "r", stdin);
 
    int n, m;
 
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> map[i][j];
        }
    }
 
    d[1][1] = map[1][1];
    d[2][1] = map[1][1] + map[2][1];
    d[1][2] = map[1][1] + map[1][2];
 
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            d[i][j] = max(max(d[i - 1][j], d[i][j - 1]), d[i - 1][j - 1]) + map[i][j];
        }
    }
 
    cout << d[n][m] << endl;
 
}