문제 링크 : www.acmicpc.net/problem/2169
2차원 배열 형태의 입력에서 목적지까지의 최대 가치를 구하는 문제이다.
문제에서 로봇은 위쪽으로 이동할 수 없다는 것에 주목하자.
로봇이 위쪽으로 이동할 수 없기 때문에, 어떤 한 행에 대한 최대 가치를 구하기 위해 그 이전 행의 최대 가치들을 미리 구해놓는다는 접근이 가능하다.
또한 로봇은 오른쪽, 왼쪽 양방향으로 이동 가능하며, 한번 지난 칸은 이동할 수 없다는 제약을 갖고 있다.
이 말은 곧 한 행에서 로봇은 오른쪽으로만 이동하거나, 왼쪽으로만 이동할 수 있다는 것과 같다.
이제 이렇게 세운 계획을 통해 구체적인 해결 방법을 구상해 보자.
■ 1행의 경우
dp의 끝 인덱스 0은 해당 값이 실제로 그 칸까지 도달하는 데의 최대 가치임을 의미한다.
■ 1행 이후의 경우
[코드]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#define MINF -99999999
using namespace std;
typedef pair<int, int> p;
int board[1001][1001];
int dp[1001][1001][3];
int n, m;
void get_dp() {
for (int row = 2; row <= n; row++) {
//좌 -> 우로 가는 최대가치 갱신
dp[row][1][1] = dp[row - 1][1][0] + board[row][1];
for (int col = 2; col <= m; col++) {
int dpval = max(dp[row - 1][col][0], dp[row][col - 1][1]) + board[row][col];
dp[row][col][1] = max(dp[row][col][1], dpval);
}
//우 -> 좌로 가는 최대가치 갱신
dp[row][m][2] = dp[row - 1][m][0] + board[row][m];
for (int col = m - 1; col >= 1; col--) {
int dpval = max(dp[row - 1][col][0], dp[row][col + 1][2]) + board[row][col];
dp[row][col][2] = max(dp[row][col][2], dpval);
}
//최종 dp값 결정
for (int col = 1; col <= m; col++)
dp[row][col][0] = max(dp[row][col][1], dp[row][col][2]);
}
}
void init() {
cin >> n >> m;
for(int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
cin >> board[i][j];
for (int k = 0; k < 3; k++) dp[i][j][k] = MINF;
}
int sum = 0;
for (int i = 1; i <= m; i++) {
for (int k = 0; k < 3; k++) dp[1][i][k] = sum + board[1][i];
sum += board[1][i];
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(NULL);
init();
get_dp();
printf("%d\n", dp[n][m][0]);
return 0;
}
|
cs |
'알고리즘 > BOJ 문제풀이' 카테고리의 다른 글
[Segtree] BOJ 7578 공장 (0) | 2020.12.22 |
---|---|
[Graph] BOJ 1766 문제집 (0) | 2020.12.21 |
[Dijkstra] BOJ 13907 세금 (0) | 2020.12.14 |
[Greedy] BOJ 9576 책 나눠주기 (0) | 2020.12.06 |
[Greedy] BOJ 1781 컵라면 (0) | 2020.12.03 |