[백준] 14585번 사수빈탕 (C++)

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

 

 

이 문제는 최대 300 X 300의 좌표평면이 주어졌을때 N개의 좌표에 대해 사탕이 존재하며 이 사탕을 최대로 먹을 수 있는 개수를 출력하는 문제이다.

 

현재 좌표에서 증가하는 좌표 방향 (x+1, y), (x, y+1) 방향으로만 갈 수 있으며 한칸을 이동할때마다 1초가 걸리며 사탕의 개수도 1씩 없어진다.

 

좌표를 전체 탐색하는 경우 O(500^2)이므로 충분히 가능하기 때문에 탑다운 방식을 사용하여 시작 좌표에서 좌표 끝까지 탐색하며

사탕을 만났을때 최댓값을 갱신하여 값을 출력하도록 하였다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int N, M;
bool arr[301][301];
int dp[301][301];

int solve(int x, int y) {
    if(x >= 301 || y >= 301) return 0;

    int &ret = dp[x][y];
    if(ret != -1) return ret;
    int cnt = (arr[x][y])? max(0, M - x - y) : 0;
    ret = max(solve(x+1, y), solve(x, y+1)) + cnt;
    return ret;
}

void input() {
    cin >> N >> M;

    memset(dp, -1, sizeof(dp));

    for(int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        arr[a][b] = true;
    }

    cout << solve(0, 0);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
}