백준 2352 반도체 설계

www.acmicpc.net/problem/2352

2352번: 반도체 설계

이 문제는 이런 유형을 아예 처음 보았다면 이것이 LIS인지 쉽게 떠올리기 어려울 수도 있다. LIS에 대한 내용은 이전 포스팅에서 정리해두었으니 참조 부탁드린다.

 

위와 같이, 1에서 시작한 선은 4로 연결되고, 3에서 시작한 선은 6에서 끝난다. 그 시작점과 끝점을 두줄에 걸쳐 나열하였다.

윗줄에 1, 2, 3, 4, 5, 6을 굳이 쓴 이유는 출발점이 증가하는 순서대로 나열되어있다는 것을 직시하기 위해서다. 

첫 번째 선이 4에서 끝나기 때문에, 그다음 선들이 3보다 작은 번호의 포트와 연결된다면 접점이 생기게 된다. 즉 이전 포트보다 항상 큰 포트와 연결되어야 한다. 그렇기 때문에, 이 문제가 갑자기 LIS문제가 되는 것이다. 

각 번호를 하나씩 보면서 들어갈 위치를 이분탐색하여 넣으면 쉽게 답을 낼 수 있다.

 

백준의 전깃줄 문제 등과 함께 이런 유형의 문제에 익숙해지면 비슷한 유형은 어렵지 않게 해결할 수 있다.

 

<주요 내용>

LIS, 가장 긴 증가하는 부분수열, 이분탐색

 

<코드>

#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;
int n,a;
vector<pair<int,int>>v;
vector<int>nv,varr;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    cin>>n;
    for(int i=0;i<n;++i){
        cin>>a;
        v.emplace_back(a,i);
    }
    sort(v.begin(),v.end());
    for(auto e:v)varr.push_back(e.second);
    nv.push_back(varr[0]);
    for(int i=1;i<(int)varr.size();++i){
        auto idx=lower_bound(nv.begin(),nv.end(),varr[i])-nv.begin();
        if(idx==(int)nv.size())nv.push_back(varr[i]);
        else nv[idx]=varr[i];
    }
    cout<<(int)nv.size()<<endl;
    return 0;
}

 

그리고 아래는 문제에서 요구하진 않았지만 실제 LIS배열을 구하는 코드이다.

첫 번째 원소에 대한 처리를 제대로 하진 않았는데, 아이디어만 확인하길 바란다.

// LIS backtrack included!

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <stack>
#define endl '\n'
using namespace std;
int idx,n,a;
vector<pair<int,int>>v;
vector<int>nv,varr;
unordered_map<int,int>um;
stack<pair<int,int>>backtrack;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    cin>>n;
    for(int i=0;i<n;++i){
        cin>>a;
        v.emplace_back(a,i+1);
        um[i+1]=a;
    }
    sort(v.begin(),v.end());
    for(auto e:v)varr.push_back(e.second);
    nv.push_back(varr[0]);
    for(int i=1;i<(int)varr.size();++i){
        idx=lower_bound(nv.begin(),nv.end(),varr[i])-nv.begin();
        if(idx==(int)nv.size())nv.push_back(varr[i]);
        else nv[idx]=varr[i];
        // LIS backtrack
        backtrack.emplace(idx,varr[i]);
    }
    idx=(int)nv.size()-1;
    while(!backtrack.empty()){
        if(backtrack.top().first==idx){
            nv[idx]=backtrack.top().second;
            idx--;
        }
        backtrack.pop();
    }
    cout<<(int)nv.size()<<endl;
    for(auto e:nv)cout<<e<<' ';
    cout<<endl;
    return 0;
}