[DP(Top-Down)] 백준 2565 전깃줄 C++

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

2565번: 전깃줄

메모이제이션

매개변수 대신 리턴값 사용

정렬 후 재귀 or LIS

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
int dp[101][501];
vector<pair<int, int>> v;

int func(int now, int before) {
    int &ret  = dp[now][before];
    if (ret != 1e9) return ret;
    if (now >= n) return 0;

    if (before < v[now].second) ret = min(func(now+1, before) + 1, func(now+1, v[now].second));
    else ret = func(now+1, before) + 1;
    return ret;
}

bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.first < b.first;
}

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

    cin >> n;

    v.resize(n, {0, 0});
    fill(&dp[0][0], &dp[100][501], (int)1e9);

    for(int i=0; i<n; i++) {
        cin >> v[i].first >> v[i].second;
    }

    sort(v.begin(), v.end(), cmp);

    cout << func(0, 0);

    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.first < b.first;
}

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

    int n;
    cin >> n;

    vector<pair<int, int>> v(n, {0, 0});
    for(int i=0; i<n; i++) {
        cin >> v[i].first >> v[i].second;
    }

    sort(v.begin(), v.end(), cmp); // 정렬 후 LIS

    vector<int> dp(n, 1);
    for(int i=1; i<n; i++) { // i 기준, j 원소 < i 원소
        for(int j=0; j<i; j++) {
            if (v[i].second > v[j].second) dp[i] = max(dp[i], dp[j] + 1);
        }
    }

    int answer = 0;
    for(int i=0; i<n; i++) answer = max(answer, dp[i]);

    cout << n - answer;
    
    return 0;
}

* 참고

// 시간초과
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, answer = 1e9;
vector<pair<int, int>> v;

void func(int now, int before, int cnt) {
    if (now >= n) {
        answer = min(answer, cnt);
        return;
    }

    if ((before == -1) || (v[before].second <= v[now].second)) func(now+1, now, cnt);
    func(now+1, before, cnt+1);
}

bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.first < b.first;
}

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

    cin >> n;

    v.resize(n, {0, 0});
    for(int i=0; i<n; i++) {
        cin >> v[i].first >> v[i].second;
    }

    sort(v.begin(), v.end(), cmp);

    func(0, -1, 0);

    cout << answer;

    return 0;
}

// 시간초과
#include <iostream>
#include <vector>

using namespace std;

int n, answer = 1e9;
vector<pair<int, int>> v;
vector<bool> check;

void dfs(int idx, int cnt) {
    if (idx >= n) {
        answer = min(answer, cnt);
        return;
    }

    bool flag = true;
    for(int i=0; i<n; i++) {
        if (!check[i]) continue;
        if ((v[i].first < v[idx].first) && (v[i].second > v[idx].second)) {
            flag = false;
            break;
        }
    }
    
    if (flag) {
        check[idx] = true;
        dfs(idx+1, cnt);
    }

    check[idx] = false;
    dfs(idx+1, cnt+1);
}

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

    cin >> n;

    v.resize(n, {0, 0});
    check.resize(n, 0);
    
    for(int i=0; i<n; i++) {
        cin >> v[i].first >> v[i].second;
    }

    dfs(0, 0);

    cout << answer;

    return 0;
}

 

// 틀림
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, answer = 1e9;
int dp[101][501];
vector<pair<int, int>> v;

void func(int now, int before, int cnt) {
    if (dp[now][before] != -1) return;
    if (now >= n) {
        answer = min(answer, cnt);
        return;
    }

    if (before < v[now].second) {
        dp[now][v[now].second] = cnt;
        func(now+1, v[now].second, cnt);
    }
    dp[now][before] = cnt+1;
    func(now+1, before, cnt+1);
}

bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.first < b.first;
}

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

    cin >> n;

    v.resize(n, {0, 0});
    fill(&dp[0][0], &dp[100][501], -1);

    for(int i=0; i<n; i++) {
        cin >> v[i].first >> v[i].second;
    }

    sort(v.begin(), v.end(), cmp);

    func(0, 0, 0);

    cout << answer;

    return 0;
}