백준 2562번 전깃줄

백준 2562번 전깃줄

#include <iostream>
#include <string>
#include<cstring>
#include<queue>
#include <vector>
#include <algorithm>
#include<cmath>
using namespace std;
 
int n;
vector<pair<int, int> > line;
int cache[501];
 
//교차하지않는 가장 많은 전깃줄을 가질 때 전깃줄 갯수 구하는 함수. 
int lis(int start, vector<pair<int, int> > line) {
    int &ret = cache[start];
    if (ret != -1) return ret;
 
    ret = 1;
    for (int next = start + 1; next < n; next++) {
        //다음 전깃줄이 교차하지 않는경우.
        if (line[start].second < line[next].second) {
            ret = max(ret, 1 + lis(next, line));
        }
    }
    return ret;
}
 
 
 
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        line.push_back(make_pair(a, b));
    }
    int num = line.size();
    sort(line.begin(), line.end());
    memset(cache, -1, sizeof(cache));
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, lis(i, line));
    }
    cout << num - ans;
    return 0;
}
 

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

전형적인 LIS 기본 문제였습니다. 

전깃줄을 제거하는 것보다 가장많을때 case를 확인하는 식으로 접근해서 쉽게 풀었습니다.

#include <iostream>
#include <string>
#include<cstring>
#include<queue>
#include <vector>
#include <algorithm>
#include<cmath>
using namespace std;
 
int n;
vector<pair<int, int> > line;
int cache[501];
 
//교차하지않는 가장 많은 전깃줄을 가질 때 전깃줄 갯수 구하는 함수. 
int lis(int start, vector<pair<int, int> > line) {
    int &ret = cache[start+1];
    if (ret != -1) return ret;
 
    ret = 1;
    for (int next = start + 1; next < n; next++) {
        //다음 전깃줄이 교차하지 않는경우.
        if (start==-1|| line[start].second < line[next].second) {
            ret = max(ret, 1 + lis(next, line));
        }
    }
    return ret;
}
 
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        line.push_back(make_pair(a, b));
    }
    int num = line.size();
    sort(line.begin(), line.end());
    memset(cache, -1, sizeof(cache));
 
    
    cout << num - lis(-1, line) +1 << endl;
    return 0;
}
 

이 코드를 사용하면 lis함수가 -1부터 시작하는 경우는 위 코드처럼 main에서 루프를 돌려주지 않아도 되서 더 편하네요. 

왜 이렇게 적용이 되는지는 알고스팟 LIS에 관한 글 참조하세요!