Study hard
(c++)백준 11048번: 이동하기 본문
[풀이]
진행할수록 범위가 좁아지므로 DP를 사용한다.
어느 방향에서 와야 값이 커지는 지 확인
점화식
DP[i][j] = Maze[i][j] + max(DP[i-1][j], max(DP[i][j-1], DP[i-1][j-1]))
#include <iostream>
#include <algorithm>//max
using namespace std;
int N, M;
int Maze[1001][1001];
int DP[1001][1001];
void solution() {
DP[1][1] = Maze[1][1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
DP[i][j] = Maze[i][j] + max(DP[i - 1][j], max(DP[i][j - 1], DP[i - 1][j - 1]));
}
}
cout << DP[N][M] << '\n';
}
int main() {
cin >> N >> M;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cin >> Maze[i][j];
}
}
solution();
}
'백준 > DP' 카테고리의 다른 글
(c++)백준 14501번: 퇴사 (0) | 2020.09.14 |
---|---|
(c++)백준 11060번: 점프 점프 (0) | 2020.09.13 |
(c++)백준 11052번: 카드 구매하기 (0) | 2020.06.10 |
(c++)백준 2011번: 암호코드 (0) | 2020.06.10 |
(c++)백준 2225번: 합분해 (0) | 2020.06.10 |