[백준] 2259번: 두더지 잡기(다이나믹 프로그래밍✨💡)

너무나도 중요한 문제이기에 두고두고 다시 풀어보면 좋은 문제이다.

처음에는 시간을 기준으로 배열을 만들어야 하나 싶었지만 1e9로 지나치게 범위가 크다.

따라서 그런 생각은 버리고 두더지 배열로 두더지를 고르냐 마냐로 선택해서 최대 개수를 구하는 방식을 고려했다.

두더지는 개수가 최대 6666개이므로 해 볼만 하다는 생각이 든다.

대신 시간에 따라 두더지를 잡을 수 있기 때문에 시간 순으로 두더지를 정렬해야 한다.

 

여기서 막혔던 점은 그렇다면 어떻게 두더지 배열을 세울까, 즉 점화식에서 다시 막혔다.

여기서는 해당 두더지를 방문한다는 전제 하에 그 이후의 최대 두더지 수를 기록하기로 한다.

그리고 이전까지는 다이나믹 프로그래밍에서는 뭔가 간격이 정해져있어서 바로 비교해야한다는 편견이 있었다.

하지만 다이나믹 프로그래밍은 메모이제이션이 핵심이기 때문에, 만약 해당 배열이 채워져 있으면 여러 개를 방문해도 값이 바로바로 나올 수 있기 때문에 뒤의 요소들을 하나씩 방문하며 최대 수를 파악한다.

for(int i = pos + 1;i <= n;i++) {
    if(possible(pos, i)) {
        ret = max(ret, dy(i) + 1);
        dp[pos] = ret;
    }
}

 

여기서 중요한 포인터 활용 방식이 있다.

int &ret = dp[pos];

해당 변수의 값을 조정하면 자동으로 해당 배열의 값도 변경하게 된다.

 

#include <iostream>
#include <vector>
#include <cmath>
#include <tuple>
#include <algorithm>
#include <cstring>
using namespace std;
vector<tuple<int,int,int>> dudeojis;
int dp[6667];
int n, s;

bool possible(int a, int b) {
    int at = get<0>(dudeojis[a]);
    int ax = get<1>(dudeojis[a]);
    int ay = get<2>(dudeojis[a]);
    
    int bt = get<0>(dudeojis[b]);
    int bx = get<1>(dudeojis[b]);
    int by = get<2>(dudeojis[b]);
    
    double dist = sqrt(pow(ax - bx, 2) + pow(ay - by, 2));
    
    
    if(dist / (float)s <= bt - at) return true;
    else return false;
}

int dy(int pos) {
    int &ret = dp[pos];

    if(ret != -1) return ret;
    ret = 0;
    for(int i = pos + 1;i <= n;i++) {
        if(possible(pos, i)) {
            ret = max(ret, dy(i) + 1);
        }
    }
    
    return ret;
}

int main() {
    cin >> n >> s;
    dudeojis.push_back({0, 0, 0});
    for(int i = 0;i < n;i++) {
        int x, y, t;
        cin >> x >> y >> t;
        dudeojis.push_back({t, x, y});
    }
    
    memset(dp, -1, sizeof(dp));
    sort(dudeojis.begin(), dudeojis.end());
    cout << dy(0) << '\n';
}