[BOJ] 14585번: 사수빈탕

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

진행 방향이 윗 방향 혹은 오른쪽 방향으로 고정되어있기 때문에 내가 어떻게 움직이던간에 특정 좌표에서 먹을 수 있는 사탕의 수는 M - x좌표 - y좌표로 고정이 됩니다. 사탕바구니를 좌표 순으로 정렬한 뒤, D[i]를 i번째 사탕바구니까지 이동할 때 먹을 수 있는 최대의 사탕의 수라고 해봅시다.

그러면 D[i]는 j(= i 전에 들릴 수 있는(=x좌표,y좌표가 모두 i번째 사탕바구니의 좌표 이하인) 사탕바구니)에 대해 max(D[j]) + max(0,M-x좌표-y좌표)입니다.

https://github.com/blisstoner/BOJ/blob/master/14585.cpp