boj 23035

JoonSimJoon·2022년 6월 28일
0

알고리즘문제풀이

목록 보기
1/1

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

문제를 읽어보면 가장 짧은 경로만 갈 수 있다니까 움직일 수 있는거리는 N+M이며 이는 문제에서 주어진 그림에서 상, 우 방향으로는 갈 수 없다는 소리다.
이를 유의해서 관점을 살짝 바꾸면 LIS 문제라는걸 쉽게 알 수 있다.
그럼 잘 풀면 된다.
pair에서의 LIS는 first에 대해 정렬을 한뒤 second에 대한 LIS를 구하면 자연스럽게 pair에 대한 LIS가 나온다.
참고로 LIS이지만 중복이 되는 LIS로 풀어야한다.
난 이거 안해서 삽질했다. ㅠ

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std; 
#define ll long long
#define INF 1e9
ll N,M,T,ans,rans;
vector< pair<ll,ll> > v,rv;
vector<ll> v2,rv2;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N>>M;
    cin>>T;
    for(ll a,b,i=0;i<T;i++){
        cin>>a>>b;
        if(a<=N && b<=M){
            v.push_back({a,b});
            rv.push_back({a,b});
        }
    }
    sort(v.begin(),v.end());
    sort(rv.begin(),rv.end());
    ll l = v.size();
    v2.push_back(-INF);
    for(ll i=0;i<l;i++){
        if(v2.back()<=v[i].second){
            v2.push_back(v[i].second);
            ans++;
        }else{
            auto it = upper_bound(v2.begin(),v2.end(),v[i].second);
            *it = v[i].second;
        }
    }
    rv2.push_back(-INF);
    for(ll i=0;i<l;i++){
        if(rv2.back()<=rv[i].second){
            rv2.push_back(rv[i].second);
            rans++;
        }else{
            auto it = upper_bound(rv2.begin(),rv2.end(),rv[i].second);
            *it = rv[i].second;
        }
    }
    cout<<max(ans,rans);
    return 0;
}```
profile
안녕하세요 :)

0개의 댓글