[백준] 12861 죄수에게 주는 뇌물

처음에 그리디라고 생각했는데 틀렸다

이 문제 메모리가 500메가라서 dp[10000][10000]를 잡고

dp를 해도 통과한다 

그리고 q가 100이라서 시간도 많이 안드나보다

테이블을 d[l][r]로 잡고

l~r까지 탈출시킬 때 최소값 이라고 생각하고 돌리자

그리고 q명의 죄수를 미리 set에 넣어두자

함수에서 l~r까지 보다가 만약 set에 있는 k라는 값을 만난다면

(r-l) + d[l][k-1] + d[k+1][r]을 구하러 가보자

그리고 ret값은 1e9로 잡아두고 만약 죄수를 아무도 못만나면

0을 리턴해줘야 식에 맞게 답을 구할 수 있다

이렇게 다 해보면 나온다!

소스코드

#include <iostream>
#include <algorithm>
#include <set>
#include <cstring>
using namespace std;
int d[10010][10010];
set<int> s;
int n, m;
int go(int l, int r) {
    if (l >= r) return 0;
    int&ret = d[l][r];
    if (ret != -1) return ret;
    ret = 1e9;
    bool ok = true;
    for (int i = l; i <= r; i++) {
        if (s.count(i)) {
            ok = false;
            int temp = (r-l) + go(l, i - 1) + go(i + 1, r);
            ret = min(ret, temp);
        }
    }
    if (ok) ret = 0;
    return ret;
}
int main() {
    memset(d, -1, sizeof(d));
    scanf(" %d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int x; scanf(" %d", &x); s.insert(x);
    }
    printf("%d\n", go(1, n));
}