프로그래밍

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

[난이도] Gold3
[유형] Greedy,Sweeping

[풀이]
1. 각 점의 시작점은 s, 끝점을 e라고 했을 때, pair 배열에 {s,1} , {e,-1}로 각각 저장 뒤
first를 기준으로 정렬한다.
2. cnt를 0으로 초기화 시키고 배열을 앞에서 부터 하나씩 순회하면서 cnt에 second 값을 더해준다.
3. 해당 점을 확인한 순간에 cnt값이 현재 겹쳐져 있는 선의 총 개수이다.
(왜냐하면 선이 시작되면 +1, 끝나면 -1을 해주므로..)

#include <cstdio>
#include <algorithm>
using namespace std;
int N;
pair<int,int> a[2000001];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        int s,e;
        scanf("%d%d",&s,&e);
        a[i]={s,1};
        a[i+N]={e,-1};
    }
    sort(a,a+2*N);
    int ans=0,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/Gold3/1689.cpp

https://codeforces.com/contest/1490/problem/A

[난이도] Div.3
[유형] Greedy

[풀이]
a[i]와 a[i+1]가 dense가 아니라면 둘중 작은 수에서 두배의 수를 더해가면서 배열에 추가해주면 된다.

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int tc,n,a[50];
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&n);
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        int ans = 0;
        for(int i=1;i<n;i++){
            int p=a[i-1],q=a[i];
            if(p>q) swap(p,q);
            if(2*p>=q) continue;
            int cur=p;
 
            for(int cur=2*p;cur<q;cur*=2){
                ans++;
            }  
        }
        printf("%d\n",ans);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round702-Div.3/A.cpp

https://codeforces.com/contest/1472/problem/D

[난이도] Div.3
[유형] Greedy

[풀이]
홀수, 짝수인 숫자를 따로 vector에 보관 후 정렬하고,
Alice 차례일때 현재 홀수중 최댓값이 짝수중 최댓값보다 크다면 홀수를 선택해서 Bob이 선택못하도록 하고,
짝수가 더크다면 짝수를 선택하는 방식으로 하는것이 Alice에게 최적이다.
Bob의 차례인 경우엔 그 반대로 하면 된다.

다른 풀이를 보고 알 수 있었는데
홀수,짝수 상관없이 정렬 후 큰 수부터 선택해도 Alice,Bob 모두 optimal 하므로 이 방식으로 풀어도 된다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
int tc,N;
int main(){
    scanf("%d",&tc);
    
    while(tc--){
        scanf("%d",&N);
        vector<ll> odd,even;
        for(int i=0;i<N;i++){
            ll v;
            scanf("%lld",&v);
            if(v%2) odd.push_back(v);
            else even.push_back(v);
        }
        sort(odd.begin(),odd.end());
        sort(even.begin(),even.end());
        
        int curo=odd.size()-1,cure=even.size()-1;
        ll alice=0,bob=0;
        for(int i=0;;i++){
            if(curo<0&&cure<0) break;
            if(i%2==0){
                if(curo<0){
                    alice+=even[cure--];
                    continue;
                }
                if(cure<0){
                    curo--;
                    continue;
                }

                if(odd[curo] <= even[cure]){
                    alice+=even[cure--];
                }else{
                    curo--;
                }
            }else{
                if(curo<0){
                    cure--;
                    continue;
                }
                if(cure<0){
                    bob+=odd[curo--];
                    continue;
                }

                if(odd[curo] >= even[cure]){
                    bob+=odd[curo--];
                }else{
                    cure--;
                }
            }
        }
        if(alice>bob) puts("Alice");
        else if(alice<bob) puts("Bob");
        else puts("Tie");
        //printf("alice:%d, bob:%d\n",alice,bob);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round693-Div.3/D.cpp

https://codeforces.com/contest/1367/problem/D

[난이도] Div.3
[유형] Greedy

[풀이]
b[i]가 0인 i에는 가장 큰 알파벳이 있다는 것을 문제의 조건을 통해 알 수 있다.
(더해줄 abs(i-j)가 없으므로).
1. 현재 배열 상태에서 b[i]가 0인 i들을 찾고 그곳에 사용할 수 있는 알파벳중 큰 순서대로 확인하면서
찾은 0의 개수보다 알파벳 개수가 크거나 같으면 그 알파벳으로 찾은 i위치에 할당한다.
2. 위에서 찾은 인덱스들은 다른 b[i]들에 영향을 주면 안되므로 거리만큼 빼줘서 영향을 제거해준다.

위 과정을 반복해서 m개를 모두 찾으면 정답 스트링을 출력한다.

#include <string>
#include <queue>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;
int tc,n,k,b[51],cnt[27];
int main(){
    scanf("%d",&tc);
    while(tc--){
        string s;
        cin >> s >> n;
        for(int i=0;i<n;i++) cin >> b[i];
        priority_queue<int> q;
        memset(cnt,0,sizeof(cnt));
        for(int i=0;i<s.size();i++){
            if(!cnt[s[i]-'a']) q.push(s[i]-'a');
            cnt[s[i]-'a']++;
        }
        string ans;
        ans.resize(n);
        int total=0;
        while(total<n){
            vector<int> t;
            for(int i=0;i<n;i++) {
                if(b[i]==0) {
                    b[i]=-1;
                    t.push_back(i);
                }
            }
            for(int i=0;i<n;i++) {
                if(b[i]==-1) continue; 
                for(auto k : t) b[i]-=abs(i-k);
            }
            while(!q.empty()){
                if(cnt[q.top()]>=t.size()){
                    for(auto k : t) ans[k]=q.top()+'a';
                    q.pop();
                    total+=t.size();
                    break;
                }
                q.pop();
            }
        }
        cout << ans << '\n';
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round650-Div.3/D.cpp

https://codeforces.com/contest/1367/problem/C

[난이도] Div.3
[유형] Greedy

[풀이]
앞에서부터 사람을 앉혀보면 된다. 최대한 왼쪽에 붙도록 앉히는게 최적이다.

#include <string>
#include <cstdio>
using namespace std;
int tc,n,k,a[200000];
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d%d",&n,&k);
        int fi=n;
        for(int i=0;i<n;i++) {
            scanf("%1d",&a[i]);
            if(a[i]==1 && fi==n) fi=i;
        }
        int cnt=fi/(k+1);
        if(fi==n) {
            cnt=1+(n-1)/(k+1);
        };
        for(int i=fi;i<n;){
            int ok=1;
            int j;
            for(j=i+1;j<=i+k&&j<n;j++) {
                if(a[j]) {
                    ok=0;
                    break;
                }
            }
            cnt+=ok&&!a[i];
            i=j;
        }
        printf("%d\n",cnt);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round650-Div.3/C.cpp

https://codeforces.com/contest/1367/problem/B

[난이도] Div.3
[유형] Greedy

[풀이]
0~N-1까지 확인하면서 i번에서 Good을 만족하지 않으면
i+1~N-1까지의 j를 확인하면서 a[i]가 j에 들어갔을 때 Good을 만족하면서
a[j]가 i에 들어갔을 때도 Good을 만족하면 swap해주는 방식으로 몇번을 swap해줘야 하는지를 세준다.
만약 바꿀 수 있는 j가 없으면 답이 없으므로 -1을 출력한다.

#include <string>
#include <cstdio>
#include <algorithm>
using namespace std;
int tc,N,a[41];
int sol(){
    int cnt =0;
    for(int i=0;i<N;i++){
        if(a[i]%2==i%2) continue;
        bool ok = 0;
        for(int j=i+1;j<N;j++){
            if(i%2==a[j]%2 && j%2==a[i]%2){
                swap(a[i],a[j]);
                cnt++;
                ok=1;
                break;
            }
        }
        if(!ok) return -1;
    }
    return cnt;
}
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&N);
        for(int i=0;i<N;i++) scanf("%d",&a[i]);
        printf("%d\n",sol());
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round650-Div.3/B.cpp

https://codeforces.com/contest/1409/problem/D

[난이도] Div.3
[유형] Greedy

[풀이]
N 제한이 10^18이기때문에 1씩 증가시켜서는 시간내에 통과가 불가능하다.
각 자릿수들의 합이 점점 작아지도록 할려면 0을 점점 늘려줘야 한다.
0을 늘리려면 10의 자리부터 자릿수 올림이 발생하도록 차례대로 숫자를 더해주면 된다.

#include <cstdio>
using namespace std;
using ll = long long;
int tc,s;
ll n,tn;
int sum(){
    int ret=0;
    ll tt=tn;
    while(tt>0){
        ret+=(tt%10);
        tt/=10;
    }
    return ret;
}
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%lld%d",&n,&s);
        ll k = 10;
        tn=n;
        while(sum()>s){
            ll r = tn%k;
            if(r!=0) tn+=k-r;
            k*=10;
        }
        printf("%lld\n",tn-n);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round667-Div.3/D.cpp

[BOJ/백준][Gold4] 2109 : 순회강연 (C++)

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

[난이도] Gold4
[유형] Greedy

[풀이]
i일에는 d가 i 이상인 강연만 할 수 있다.
앞에서부터 생각하면 복잡하므로 뒤에서부터 가능한 강연료를 우선순위 큐에 추가하면 된다.
10000일이 최대이므로 i를 10000 ~ 1로 순회하면서 d가 i인 강연의 강연료 p를 우선순위 큐에 push하고
1개를 뽑으면 i일에 할 수 있는 최적의 강연을 뽑을 수 있다.

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int N,ans;
vector<int> a[10001];
int main(){ 
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        int p,d;
        scanf("%d%d",&p,&d);
        a[d].push_back(p);
    }
    priority_queue<int> pq;
    for(int i=10000;i>0;i--){
        for(auto k : a[i]) pq.push(k);
        if(!pq.empty()){
            ans+=pq.top();
            pq.pop();
        }
    }
    printf("%d",ans);
}

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