각 정점에서 최대로 가져올 수 있는 사탕의 개수를 구해서 (n,m)
까지 이르렀을 때 저장된 최댓값을 return 하면 된다. 사탕의 개수는 (1,1)
부터 (n,m)
까지 저장되어 있기 때문에 위에서 부터 top-down 방식으로 memoization 기법을 사용한다.
#include <iostream> #include <algorithm> using namespace std; const int MAX = 1001; int maze[MAX][MAX]; int dp[MAX][MAX]; int n, m; void countCandy() { for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { int sum = max({ dp[i-1][j-1], dp[i-1][j], dp[i][j-1] }); dp[i][j] = sum + maze[i][j]; } } } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> maze[i][j]; countCandy(); cout << dp[n][m] << endl; return 0; }