프로그래밍

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

[난이도] Gold1
[유형] 스위핑

[풀이]
가로 선분들과 세로 선분들을 나눠서 생각해보면
결국 가로 선분이 최대 몇개 겹칠 수 있는지, 세로 선분이 최대 몇개 겹칠 수 있는지를 각각 구해서
둘중 최댓값을 정답으로 출력하는 문제입니다.
번갈아 가면서 입력되는 가로 선분과 세로 선분을 각각 vector에 저장해줍니다.
a[i%2].push_back({l,1});
a[i%2].push_back({r,-1});
위와 같이 이런 스위핑 문제를 풀때 자주 사용하는 누적합 개념을 이용합니다.
선분이 시작되는 점에서 1을 더해주고 선분이 끝나는 점에서 1을 빼주면 어느 점에서 최대로 겹치는지
확인이 가능합니다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n,ans;
pair<int,int> p[100000];
vector<pair<int,int>> a[2];
int main(){ 
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d%d",&p[i].first,&p[i].second);
    for(int i=1;i<=n;i++){
        int l,r,q=i,z=i-1;
        if(q==n) q=n-1,z=0;
        if(p[q].first==p[z].first) {
            l=min(p[q].second,p[z].second);
            r=max(p[q].second,p[z].second);
        }else{
            l=min(p[q].first,p[z].first);
            r=max(p[q].first,p[z].first);            
        }
        a[i%2].push_back({l,1});
        a[i%2].push_back({r,-1});
    }
    for(int i=0;i<2;i++){
        sort(a[i].begin(),a[i].end());
        int tmp=0;
        for(auto [t,v] : a[i]){
            tmp+=v;
            ans=max(tmp,ans);
        }
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold1/17611.cpp

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

[난이도] Gold5
[유형] 스위핑

[풀이]
pair 배열에 (시작점,끝점)을 넣어둔 뒤, 시작점을 기준으로 오름차순을 해줍니다.
그 뒤에 스위핑을 이용하여 겹치는 부분을 처리해서 하나의 선분으로 묶어주면
전체 길이를 쉽게 구할 수 있습니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int N;
pair<int,int> v[100000];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d%d",&v[i].first,&v[i].second);
    sort(v,v+N);
    int ans=0,s=v[0].first,e=v[0].second;
    for(int i=0;i<N;i++){
        if(v[i].first <= e) {
            if(v[i].second > e) e=v[i].second;
        }else{
            ans+=e-s;
            s=v[i].first;
            e=v[i].second;
        }
    }
    printf("%d",ans+e-s);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/15922.cpp

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

[난이도] Gold3
[유형] 스위핑

[풀이]
일단 좌측 x값을 기준으로 정렬을 한다.
y와 관계없이 (xi1,xi2) (xj1,xj2)가 이동 가능한 점이려면
x12>=xj1 를 만족하면 된다.
즉, y와 상관없이 연속된 직선상에 포함되는 점들은 이동이 가능한 점(집합)이다.

스위핑을 해주면서 어떤 그룹에 속하는지 배열에 저장하면 답을 찾을 수 있다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
int N,Q;
struct P{
    int x1,x2,num;
};
bool cmp(P a,P b){
    return a.x1 < b.x1;
}
P tree[100001];
int g[100001];
int main(){
    scanf("%d%d",&N,&Q);
    for(int i=0;i<N;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        tree[i]={a,b,i};
    }
    sort(tree,tree+N,cmp);

    int sid=0,e=tree[0].x2;
    g[0]=sid;

    for(int i=1;i<N;i++){
        if(tree[i].x1<=e){
            if(tree[i].x2>e) e=tree[i].x2;    
        }else{
            sid++;
            e=tree[i].x2;
        }
        g[tree[i].num]=sid;
    }
    while(Q--){
        int u,v;
        scanf("%d%d",&u,&v);
        u--,v--;
        if(g[u]==g[v]) puts("1");
        else puts("0");
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/17619.cpp

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

[난이도] Gold5
[유형] 스위핑

[풀이]
1. pair 배열에 {Si+1,-1}, {Ti,1} 로 분할하여 저장한 뒤 오름차순으로 정렬한다.
2. cnt 변수를 선언하고 여기에는 현재 시간에 동시에 진행중인 수업의 개수(필요한 강의실 수)가 저장되게 된다.
3. cnt 변수를 업데이트 하는 방법은 정렬된 배열 a를 0~2N-1 순서로 차례로 순회하면서
second (-1또는 1) 값을 cnt에서 빼준다. Si (시작) 일때는 새로운 강의가 추가되므로 1을 더해주고
Ti 일때는 강의가 끝나느 것이므로 1을 빼주는 것이다. 정렬할 때 Si에 -1을 넣은 것은 오름차순으로 정렬시 Si가 먼저 오게 하기 위함이다.
이런 식으로 순회하면서 cnt를 업데이트할때, cnt가 가장 큰 값이 나오는 순간이 필요한 강의실 수가 가장 많은 순간이고
필요한 최대 강의실 수가 된다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N,ans;
pair<int,int> a[400001];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        int s,e;
        scanf("%d%d",&s,&e);
        a[i]={s+1,-1};
        a[i+N]={e,1};
    }
    sort(a,a+2*N);

    int cnt=0;
    for(int i=0;i<2*N;i++){
        cnt-=a[i].second;
        ans=max(cnt,ans);
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/11000.cpp

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

[난이도] Gold2
[유형] 스위핑

[풀이]
길이 d의 선을 평행이동 시키면서 어느시점에 i가 포함되고 빠지는지를 누적하면서 계산해주면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N,d,ans;
vector<pair<int,int>> t,a;
int main(){
    scanf("%d",&N);
    int j=0;
    for(int i=0;i<N;i++){
        int u,v;  
        scanf("%d%d",&u,&v);
        if(u>v) swap(u,v);
        t.push_back({u,v});
    }
    scanf("%d",&d);

    for(auto p : t){
        if(p.second-p.first>d) continue;
        a.push_back({p.first,1});
        a.push_back({p.second-d,-1});
    }
    sort(a.begin(),a.end());
    int cnt=0;
    for(auto p : a){       
        cnt-=p.second;
        ans=max(ans,cnt);
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold2/13334.cpp

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

[난이도] Gold3
[유형] 스위핑

[풀이]
idea : 1) 어차피 M까지 가야하므로 정방향으로 가는 사람들은 고려할 필요가 없다.
2) 반대로 가는 사람들 때문에 돌아가야하는 추가 이동거리가 발생하는데,
5->2, 6->3 이렇게 겹치는 경로가 있는 사람들끼리 묶어서 뒤로 이동하는것이 가장 효율적이다.
3) a>b인 (a,b) 입력에 대해 (b,a) pair로 vector에 저장 뒤 정렬 후,
스위핑을 해주면서 묶인 집합의 길이*2를 답에 더해주면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
int N;
ll M;
vector<pair<ll,ll>> v;
int main(){
    scanf("%d%lld",&N,&M);
    for(int i=0;i<N;i++) {
        ll u,r;
        scanf("%lld%lld",&u,&r);
        if(u>r) v.push_back({r,u});
    }
    sort(v.begin(),v.end());

    ll s=v[0].first, e=v[0].second;
    for(auto p : v){
        if(e<p.first){
            M+=2*(e-s);
            s=p.first,e=p.second;
        }else if(e<p.second){
            e=p.second;
        }
    }
    M+=2*(e-s);
    printf("%lld",M);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/2836.cpp

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

[난이도] Gold5
[유형] 스위핑

[풀이]
1. pair 배열 에 (시작점,끝점)으로 저장 뒤 시작점을 기준으로 오름차순 정렬한다.
2. s:현재 긋고 있는 선의 시작점, e:현재 긋고 있는 선의 끝점
3. 앞에서부터 pair 의 선들을 확인하면서 선이 s~e에 포함되면 skip, 선의 앞이 e보다 작거나 같고 뒤가 e보다 큰 경우
e를 업데이트, 선의 앞이 e보다 크면 e-s를 답에 저장하고 s,e를 새로 업데이트.

위 방식으로 누적된 길이가 그리는 선의 최종 길이이다.

#include <cstdio>
#include <algorithm>
using namespace std;
int N;
pair<int,int> a[1000000];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d%d",&a[i].first,&a[i].second);
    
    sort(a,a+N); 
    int s=a[0].first,e=a[0].second;
    int d=0;
    for(int i=1;i<N;i++){
        if(a[i].first<=e) {
            if(e<a[i].second) e=a[i].second;
        }
        else {
            d+=e-s;
            s=a[i].first;
            e=a[i].second;
        } 
    }
    d+=e-s;
    printf("%d",d);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/2170.cpp