BOJ 2169: 로봇 조종하기

https://www.acmicpc.net/problem/2169

  • 2월동안 187문제 풀기(지난달 누적 87개) (35/187)
  • 그래도 꽤 고심한 DP 유형. 잘 풀리니 기분이 좋다.
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
#include <bits/stdc++.h>
using namespace std;

const int SZ = 1000;
int N, M;
int arr[SZ+9][SZ+9];
int dpL[SZ+9];
int dpR[SZ+9];
int save[SZ+9];

void fillInput() {
  ios::sync_with_stdio(false);
  cin >> N >> M;
  for(int i = 0; i < N; i++)
    for(int j = 0; j < M; j++)
      cin >> arr[i][j];
}

int main() {
  fillInput();
  save[0] = arr[0][0];
  for(int i = 1; i < M; i++)
    save[i] = save[i-1] + arr[0][i];

  for(int i = 1; i < N; i++) {
    dpL[0] = save[0] + arr[i][0];
    dpR[M-1] = save[M-1] + arr[i][M-1];
    for(int j = 1; j < M; j++) {
      int r = M-1-j;
      dpL[j] = max(save[j], dpL[j-1]) + arr[i][j];
      dpR[r] = max(save[r], dpR[r+1]) + arr[i][r];
    }
    for(int j = 0; j < M; j++)
      save[j] = max(dpL[j], dpR[j]);
  }
  cout << save[M-1];
  return 0;
}