https://www.acmicpc.net/problem/3114
(1, 1)에서 출발하여 (N, M)에 도착했을 때 사과 + 바나나의 최대를 구하는 문제입니다.
이동은 아래, 오른쪽, 오른쪽 + 아래 만 가능합니다.
(x, y) 기준 사과 + 바나나의 합은
1. (x, y) ~ (x - 1, y) 까지는 바나나
2. (x + 1, y) ~ (N, y) 까지는 사과
두개를 더하여 계산합니다.
그렇다면 사과와 바나나의 누적합은 각각 구할 수 있고, 세로별로 누적합을 구하도록 합니다.
세팅이 완료되었다면 점화식을 구해봅니다.
이동 가능한 방향이 어떻게 되는지를 이용하면 (x, y) 기준 3개 중 하나를 답으로 가져갈 수 있습니다.
(x - 1, y - 1), (x, y - 1)에서 왔을 경우 y 좌표가 바꼈으므로 이전에 구했던 누적합을 더하면 됩니다.
(x - 1, y)에서 왔을 경우 y좌표가 바뀌지 않았으므로 누적합 범위를 조정해야 합니다.
dp 값을 채워나가는 도중에 dp[N][M]보다 커지는 경우가 있을 수 있으니 dp[N][M]를 명시하여 출력해주시면 되겠습니다.
|
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
|
#include <iostream>
#include <algorithm>
#define MAX 1501
using namespace std;
int sumA[MAX][MAX], sumB[MAX][MAX], dp[MAX][MAX];
int N, M;
void func() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (j == 1) {
dp[i][j] = sumA[N][j] - sumA[i][j];
continue;
}
int tmp = sumA[N][j] - sumA[i][j] + sumB[i - 1][j];
dp[i][j] = max(max(dp[i - 1][j - 1], dp[i][j - 1]) + tmp, dp[i - 1][j] - sumA[i][j] + sumA[i - 1][j]);
}
}
cout << dp[N][M] << '\n';
}
void input() {
char ch;
int x;
cin >> N >> M;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cin >> ch >> x;
if (ch == 'A') {
sumA[i][j] = x;
}
else {
sumB[i][j] = x;
}
sumA[i][j] += sumA[i - 1][j];
sumB[i][j] += sumB[i - 1][j];
}
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 2216 문자열과 점수 (0) | 2024.06.28 |
|---|---|
| boj 1354 무한 수열 2 (0) | 2024.06.27 |
| boj 11560 다항식 게임 (0) | 2024.06.13 |
| boj 28018 시간이 겹칠까? (0) | 2023.08.08 |
| boj 12841 정보대 등산 (0) | 2023.07.31 |