백준 알고리즘 11048번 : 이동하기

링크

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

sol1) dp

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

int board[1001][1001],dp[1001][1001];

int main() {
  fastio;
  int n,m; cin >> n >> m;
  for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) cin >> board[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 - 1][j - 1]}) + board[i][j];
  }
  cout << dp[n][m] << "\n";
  return 0;
}

가져갈 수 있는 사탕의 "최댓값"을 가져가야 하고, 이동은 (r + 1,c),(r,c + 1),(r + 1,c + 1) 이렇게 3방향으로 이동을 할 수 있다고 하였으니 최댓값을 가져가기 위해선 max(3방향 중에서 가장 큰 값) + (현재까지 가져온 사탕의 수) 이렇게 세울 수 있습니다 따라서 dp식은
dp[i][j] = max({dp[i - 1][j],dp[i][j - 1],dp[i - 1][j - 1]}) + board[i][j] 이렇게 세울 수 있습니다.