코드 복사/붙여넣기 하는 당신이 아름답습니다.

3114 : 사과와 바나나

풀이

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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-10-02 11:11

Read more posts by this author