그리디(3) - 강의실 배정, 선 긋기, 수 묶기

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

11000번: 강의실 배정

자력솔에 실패했다. 가장 많은 강의가 있는 시간대의 강의의 수를 구한다. 

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

vector<pair<int,int>> arr;
int n,s,t,cnt;

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s>>t;
        arr.push_back({s,1});
        arr.push_back({t,-1});
    }
    sort(arr.begin(),arr.end());
    
    int ans=0; //필요한 강의실의 수
    int curTime=arr[0].X; //현재 시간
    int cur=0; //현재 시간에 열려있는 강의실 수
    int idx=0; //현재 보고있는 arr 인덱스
    
    while(1){

        //같은 시간대에 일어나는 일을 모두 탐색함, idx가 범위 넘기면 나감
        while(idx<2*n && arr[idx].X==curTime){
            cur+=arr[idx].Y;
            idx++;
        }
        ans=max(cur,ans); //ans 갱신
        if(idx==2*n) break; //다 탐색했으면 break;
        curTime=arr[idx].X;
    }
    return 0;
}

---

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

2170번: 선 긋기

자력솔에 해냈다. 강의실 배정과 비슷한 느낌으로 풀었다.

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

vector<pair<int,int>> arr;
int n,x,y;

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x>>y;
        if(x>y) swap(x,y);
        //작은 값(시작점)이 1
        //큰 값(도착점)이 -1
        arr.push_back({x,1});
        arr.push_back({y,-1});
    }
    sort(arr.begin(),arr.end());

    int ans=0;
    int st=arr[0].X; //시작값
    int cnt=1; //0이 되면 선 하나가 그어진 것임
    for(int i=1;i<arr.size();i++){
        cnt+=arr[i].Y;
        if(!st && arr[i].Y) st=arr[i].X;
        if(!cnt){
            ans+=(arr[i].X-st);
            st=0;
        }
    }
    cout<<ans;
    return 0;
}

---

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

1744번: 수 묶기

풀다가 아무리 생각해도 이런 방식이 아닌 것 같아서 포기했다.

일단 0 -1이 아니면 곱셈을 하는게 무조건 이득이다.

그래서 0 이하와 나머지를 각각 다른 vector에 분리시켜서 계산한다.

오름차순 정렬 후 뒤쪽의 큰 수부터 쌍을 지어 곱해나가야 하는데, 0과 -1의 경우는 내림차순 정렬을 해서 0 -1 -1 이런 식으로 만들면 양수만 저장된 vector와 같은 방식으로 계산해 결과를 도출할 수 있다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans;
void seqSum(vector<int> v){
    while(v.size()>1){
        ans += (*(v.end()-1) * *(v.end()-2));
        v.pop_back();
        v.pop_back();
    }
    if(v.size()==1) ans+=v[0];
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    vector<int> seqP, seqN;
    int n; cin>>n;
    for(int i=0;i<n;i++){
        int t; cin>>t;
        if(t==1) ans++; //1은 곱셈 연산에 사용되지 않으므로 그냥 ans에 더함
        else if(t<=0) seqN.push_back(t); //0과 -1은 N에 넣고
        else seqP.push_back(t); //양수는 P에 넣고
    }
    sort(seqP.begin(),seqP.end()); 
    sort(seqN.begin(),seqN.end(),greater<>());
    seqSum(seqP);
    seqSum(seqN);
    cout<<ans;
    return 0;
}

---