백준 11048 - 이동하기
생각 및 접근
- 아주 전형적인 동적 프로그래밍 문제
- 값을 입력받을 배열
arr
과 동적 프로그래밍 결과를 저장하는 배열dp
를 선언하였다. dp[i][j]
에는 (i, j)까지 탐색했을 때 가장 많은 사탕을 받을 수 있을 때, 가지고 있는 사탕의 수를 저장한다.- 준규는 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 갈 수 있으므로 위쪽 왼쪽부터 아래쪽 오른쪽 순서로 dp 탐색을 하면 될 것 같다.
dp[i - 1][j] + arr[i][j]
,dp[i - 1][j - 1] + arr[i][j]
,dp[i][j - 1] + arr[i][j]
중에서dp[i][j]
에 가장 큰 값을 저장하면 된다.
코드
#include <bits/stdc++.h>
using namespace std;
int n, m, arr[1001][1001], 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 >> arr[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] = max(dp[i][j], dp[i - 1][j - 1]);
dp[i][j] += arr[i][j];
}
}
cout << dp[n][m];
}
채점 결과
'Coding Test > acmicpc' 카테고리의 다른 글
백준 15989 - 1, 2, 3 더하기 4 (c++) (0) | 2020.08.12 |
---|---|
백준 1890 - 점프 (c++) (0) | 2020.08.10 |
백준 2580 - 스도쿠 (c++) (0) | 2020.08.09 |
백준 14502 - 연구소 (c++) (0) | 2020.08.07 |
백준 1759 - 암호 만들기 (c++) (0) | 2020.08.05 |