✅ DP

문제

1. 해결 로직

• 한 위치에서 이동가능 한 방향이 3가지이므로 브루트포스로 풀면
  3^1000000 번이 걸린다. 시간초과가 날게 분명하므로 다른 방법이 필요하다.
  특정 위치까지 사탕의 최댓값은 정해져 있으므로 DP를 사용한다.

• 대각선에서 온 경우는 생각하지 않아도 된다. 왜냐하면 사탕을 최대로 가져야 하기 때문에 대각선에서 한번에 오는 것보다 위나 왼쪽에서 한칸이라도 더 거쳐서 오는게 이득이기 때문이다.

2. 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int N, M;
int map[1001][1001];
int dp[1001][1001];

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

    cin >> N >> M;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            cin >> map[i][j];
        }
    }

    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            dp[i][j] += map[i][j];
        }
    }

    cout << dp[N][M] << "\n";

    return 0;
}

3. 시간 복잡도

$O(N*M)$ 이므로 $O(N^2)$

4. Review

DP를 떠올리는게 중요했던 문제

5. Reference