[백준] 14585 사수빈탕

(301,301) 까지 가면서 다 보면 된다

처음에 d[300][300][600] 해서 시간까지 테이블로 잡으려다가 

메모리 보고 포기했다 ㅎㅎ

시간을 잡지않아도 (0,0)에서 위,오른쪽만 움직이기 때문에

시간 = x+y가 된다. 따라서 m-x+y가 현재위치에서의 사탕 수 이다

소스코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int d[303][303];
bool arr[303][303];
int n, m;
 
int go(int x, int y) {
    if (x >= 301 || y >= 301) return 0;
    int&ret = d[x][y];
    if (ret != -1) return ret;
    int cnt = (arr[x][y]==true) ? max(0,m - x - y) : 0;
    ret = max(go(x + 1, y), go(x, y + 1)) + cnt;
    return ret;
}
 
int main() {
    memset(d, -1, sizeof(d));
    scanf(" %d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        int x, y; scanf(" %d %d", &x, &y);
        arr[x][y] = true;
    }
    printf("%d\n", go(0, 0));
 
}