[BOJ] 전깃줄

[BOJ] 전깃줄

Problem URL : 전깃줄

[1] 동적 프로그래밍을 이용한 풀이

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

using namespace std;

int n;
vector<pair<int, int>> pole;
// dp[i]는 수열의 i번째 원소를 마지막으로 하는 부분수열중 최장 길이
int dp[100]; 


int main()
{   
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    int a, b;
    for (int i = 0; i < n; i++)
    {
        cin >> a >> b;
        pole.push_back({ a,b });
    }
    sort(pole.begin(), pole.end());

    dp[0] = 1;
    for (int i = 1; i < n; i++)
    {
        dp[i] = 1;
        for (int j = 0; j < i; j++)
        {
            if (pole[i].second > pole[j].second && dp[i] < dp[j] + 1)
            {
                dp[i] = dp[j] + 1;
            }
        }
    }

    int lis = 1;
    for (int i = 1; i < n; i++)
    {
        if (lis < dp[i]) {
            lis = dp[i];
        }
    }

    cout << n - lis << '\n';
}

[2] lower bound를 이용한 풀이

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

using namespace std;

int n;
vector<pair<int, int>> pole;
// cache[n] = 최장증가수열의 (n+1)번째 항
vector<int> cache;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    int a, b;
    for (int i = 0; i < n; i++)
    {
        cin >> a >> b;
        pole.push_back({ a,b });
    }
    sort(pole.begin(), pole.end());
    for (int i = 0; i < n; i++){
        int value = pole[i].second;
        if (cache.empty() || cache.back() < value) {
            cache.push_back(value);
        }else {
            int idx = lower_bound(cache.begin(), cache.end(), value) - cache.begin();
            cache[idx] = value;
        }
    }

    cout << n - cache.size() << '\n';
}

[3] segmentTree를 이용한 풀이

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#define p pair<int,int>

using namespace std;
const int MAX = 1 << 9;

int segtree[2 * MAX];

void update(int x, int num) {
	segtree[x] = num;
	while (x / 2 > 0) {
		x /= 2;
		segtree[x] = max(segtree[2 * x], segtree[2 * x + 1]);
	}
}
int query(int position, int idx = 1, int s = 1, int e = MAX) {
	if (s > position) return 0;
	if (e <= position) return segtree[idx];

	int mid = (s + e) / 2;
	return max(query(position, 2 * idx, s, mid), query(position, 2 * idx + 1, mid + 1, e));
}

int main() {
	ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	memset(segtree, 0, sizeof(segtree));
	int n;
	cin >> n;
	
	priority_queue<p, vector<p>, greater<p>> pq;
	for (int i = 0; i < n; ++i) {
		int position;
		int value;
		cin >> position >> value;
		pq.push({ value, position });
	}
	int ans = 0;
	while (!pq.empty()) {
		int value = pq.top().first;
		int position = pq.top().second;
		pq.pop();
		int t = query(position);
		ans = max(ans, t + 1);
		update(MAX + position, t + 1);
	}
	cout << n - ans << '\n';
		
	return 0;
}

Comments

LIS(Longest Increasing Subsequence) 최장 증가 부분 수열 문제이다. [3] seg[x] : x위치의 수열 값을 끝으로 하는 증가 수열의 최대 길이
이 블로그 를 참조하였다