220720 백준 BOJ 풀이 : LIS (가장 긴 증가하는 부분 수열) 문제들

백준 BOJ 2568번 : 전깃줄 - 2

문제 난이도 : Platinum V

알고리즘 분류 : LIS (가장 긴 증가하는 부분 수열)

 

 

 

위의 그림처럼 전깃줄의 연결 상태가 주어질 때, 교차하는 전깃줄이 없도록 만들기 위해 제거해야 하는 전깃줄의 수가 최소인 경우 제거해야 할 전깃줄의 A에 연결된 번호들을 오름차순으로 구하는 문제이다.

 

A와 연결된 번호들을 오름차순으로 정렬했을 때, B와 연결된 번호들도 오름차순이라면 교차하는 선분이 없다는 것이다.

따라서, A의 위치들에 대해 오름차순으로 정렬하고 B의 위치들에 대해 LIS를 구한 뒤 이에 포함되지 않는 원소들을 찾아 다시 A와 연결되는 위치로 가서 해당 번호들을 제거해주면 된다.

 

연결 관계가 이중으로 되어있고 A의 번호와 B의 번호를 고려해야하며, 모든 번호에 전깃줄이 연결되어있는 것이 아니라 다소 구현이 까다로웠다.

조금 우회적으로 풀었을 수는 있지만 아래의 코드를 참고하면 좋을 것이다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    vector<pair<int, int>> p(N);
    for(int i=0; i<N; i++) cin >> p[i].first >> p[i].second;

    sort(p.begin(), p.end());

    vector<int> v(N);
    for(int i=0; i<N; i++) v[i] = p[i].second;

    vector<int> u;
    u.push_back(v[0]);

    int cnt = 0;

    vector<pair<int, int>> dp(N);
    dp[0] = {v[0], 0};

    for(int i=1; i<N; i++) {
        if(v[i] > u.back()) {
            u.push_back(v[i]);
            cnt++;

            dp[i] = {v[i], cnt};
        }
        else {
            int x = lower_bound(u.begin(), u.end(), v[i]) - u.begin();
            u[x] = v[i];

            dp[i] = {v[i], x};
        }
    }

    vector<int> w;

    for(int i=N-1; i>=0; i--)
        if(cnt == dp[i].second) {
            w.push_back(dp[i].first);
            cnt--;
        }

    vector<int> rl(500001);
    for(int i=0; i<N; i++) rl[p[i].second] = p[i].first;

    vector<bool> b(500001);
    for(int i=0; i<w.size(); i++) b[rl[w[i]]] = true;

    vector<int> ans;
    for(int i=0; i<N; i++)
        if(!b[p[i].first]) ans.push_back(p[i].first);

    cout << ans.size() << "\n";
    for(int i=0; i<ans.size(); i++) cout << ans[i] << "\n";
}

 

 

백준 BOJ 2550번 : 전구

문제 난이도 : Gold III

알고리즘 분류 : LIS (가장 긴 증가하는 부분 수열)

 

스위치와 전구가 각각 1~N까지의 번호를 가지고 있으며 직선으로 연결된다고 할 때, 두 스위치의 전선이 교차하는 경우 스위치의 불이 켜지지 않는다고 가정하면 스위치를 동시에 눌러서 전구를 최대한 많이 켤 수 있는 스위치들의 번호를 구하는 문제이다.

 

스위치의 번호를 오름차순으로 바꿔주면 전구의 번호를 나타내는 수열에서 LIS(가장 긴 증가하는 부분 수열)를 선택하는 문제로 치환할 수 있다.

왜냐하면 스위치가 오름차순으로 배정되었으므로 두 전구의 숫자가 작아진다는 것은 전선이 교차되었음을 의미하기 때문이다.

 

따라서 LIS를 O(N log N) 시간에 수행하는 코드를 활용하여, 스위치와 전구의 번호를 바꿔주는 부분만 구현하여 AC를 받을 수 있었다.

다만 번호를 재배정하는 과정에서 벡터를 여러 개 선언해야 해서 코드가 복잡하게 보이는 경향이 있다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    vector<int> w(N+1), wr(N+1);
    for(int i=0; i<N; i++) {
        int x; cin >> x;

        w[x] = i+1;
        wr[i+1] = x;
    }

    vector<int> v(N);
    for(int i=0; i<N; i++) {
        int x; cin >> x;

        v[i] = w[x];
    }

    vector<int> u;
    u.push_back(v[0]);

    int cnt = 0;

    vector<pair<int, int>> dp(N);
    dp[0] = {v[0], 0};

    for(int i=1; i<N; i++) {
        if(v[i] > u.back()) {
            u.push_back(v[i]);
            cnt++;

            dp[i] = {v[i], cnt};
        }
        else {
            int x = lower_bound(u.begin(), u.end(), v[i]) - u.begin();
            u[x] = v[i];

            dp[i] = {v[i], x};
        }
    }

    vector<int> ans;

    for(int i=N-1; i>=0; i--)
        if(cnt == dp[i].second) {
            ans.push_back(dp[i].first);
            cnt--;
        }

    vector<int> ansr;
    for(int i=ans.size()-1; i>=0; i--) ansr.push_back(wr[ans[i]]);

    sort(ansr.begin(), ansr.end());

    cout << ansr.size() << "\n";
    for(int i=0; i<ansr.size(); i++) cout << ansr[i] << " ";
}

 

 

백준 BOJ 16200번 : 해커톤

문제 난이도 : Silver IV

알고리즘 분류 : 정렬, 그리디

 

길이 N인 수열이 주어지고, 원소들을 적절히 묶어 그룹들을 만들 때 원소 a_i는 원소가 a_i개 이하로 구성된 그룹에만 속할 수 있다고 한다면 최소 그룹의 수는 얼마인지 구하는 문제이다.

 

원소들의 성질에 대해 생각해보면 어떤 그룹의 크기를 결정하는 것은 그 그룹에서의 가장 작은 원소의 값이다.

따라서 원소들을 오름차순으로 정렬하고, 작은 것부터 그룹의 원소 수가 최대한 많게 그리디적으로 구성해보면 답을 얻을 수 있다.

나의 경우에는 a_i 값만큼 그룹의 크기를 형성할 수 있으므로, i += v[i]와 같이 i 값을 갱신해가면서 ans++로 count 해주었다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    vector<int> v(N);
    for(int i=0; i<N; i++) cin >> v[i];

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

    int ans = 0, i = 0;

    while(i < N) {
        i += v[i];
        ans++;
    }

    cout << ans << "\n";
}