Search
Duplicate

이동하기

주차
13
문제번호
11048
언어
티어
실버
유형
DP
nj_Blog
nj_상태
완료
이해도
풀이
사람
이해도 2
13 more properties

Memo

1, 1부터 열, 행 순으로 순회하면서 자신의 위치로 올 수 있는 값들 중에 최대값과 현재 자신의 위치의 값을 더합니다.

Code

제출 날짜

@3/24/2021

메모리

9844 KB

시간

64 ms
#include <iostream> #include <algorithm> int N, M; int dp[1001][1001]; int maze[1001][1001]; void input_faster() { std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); } void input() { input_faster(); std::cin >> N >> M; for (int i = 1 ; i <= N ; i++) for (int j = 1; j <= M ; j++) std::cin >> maze[i][j]; } void solve() { for (int i = 1 ; i <= N ; i++) for (int j = 1 ; j <= M ; j++) dp[i][j] = std::max({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + maze[i][j]; } void print_val() { std::cout << dp[N][M]; } int main() { input(); solve(); print_val(); return (0); }
C++
복사