풀이
A는 prefix 누적합, B는 suffix 누적합을 구해주자.
불도저가 [i][j]로 오는 방법은
[i-1][j-1], [i-1][j], [i][j-1] 이 세 가지가 있다.
모든 i, j를 돌면서, 위의 세 가지 경우에 대해 최댓값을 계산해주자.
i=1이거나 j=1인 경우의 예외 케이스에 주의하자.
코드
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
int n, m, i, j, a[1502][1502], b[1502][1502], d[1502][1502];
char s[9];
int main() {
scanf("%d %d", &n, &m);
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
scanf("%s", s);
(s[0]=='A' ? a[i][j] : b[i][j]) += atoi(s+1);
}
}
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
a[i][j] += a[i][j-1];
b[i][m-j+1] += b[i][m-j+2];
}
}
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
if (i == 1 || j == 1) {
d[i][j] = d[i-1][j] + b[i][j+1];
continue;
}
d[i][j] = max(d[i-1][j-1], d[i-1][j]) + a[i][j-1] + b[i][j+1];
d[i][j] = max(d[i][j], d[i][j-1] - b[i][j] + b[i][j+1]);
}
}
printf("%d\n", d[n][m]);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이