BOJ 2169: 로봇 조종하기 작성일 2020-02-18 https://www.acmicpc.net/problem/2169 2월동안 187문제 풀기(지난달 누적 87개) (35/187) 그래도 꽤 고심한 DP 유형. 잘 풀리니 기분이 좋다. 1234567891011121314151617181920212223242526272829303132333435363738#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; }