프로그래밍

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

[난이도] Gold3
[유형] Greedy

[풀이]
pi가 항상 wi보다 크기 때문에 어떤 당근 i를 마지막 한번만 뽑아 먹는 것이 이득입니다.
중간에 뽑아서 다시 심게 되면 영양분이 p만큼 증가해야 되는 날에 다시 심게 되면서 w만 증가하게 되기 때문입니다.
결국 모든 당근을 한번씩만 뽑아먹어야 한다면, p가 클 수록 나중에 뽑아 먹는 것이 이득입니다.
p가 같다면 w가 큰 것을 선택해야 합니다.

정렬을 이용해 큰 (p,w) 부터 뽑으면서 계산한 뒤 정답에 더해주면 됩니다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N,T;
vector<pair<int,int>> v;
int main(){
    scanf("%d%d",&N,&T);
    for(int i=0;i<N;i++) {
        int w,p;
        scanf("%d%d",&w,&p);
        v.push_back({p,w});
    }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());

    long long ans=0;
    for(int i=0;i<N;i++){
        auto [p,w] = v[i];
            ans+=w+(long long)p*(T-i-1);
    }
    printf("%lld",ans);
}

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

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

[난이도] Gold4
[유형] Greedy

[풀이]
순위가 낮은 (숫자 큰) 사람을 빠르게 경기를 시켜서 빠르게 탈락시킬수록
랭킹의 차이의 합을 최소로 만드는데 유리하므로
경기를 매칭 시킬 때, 현재 남은 사람중에 랭킹이 가장 낮은 선수를 무조건 포함시켜 주는 방식으로
풀면 최적의 경우가 됩니다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N,ans;
int main(){
    scanf("%d",&N);
    vector<int> v(N);
    for(int i=0;i<N;i++) scanf("%d",&v[i]);
    while(v.size()>1){
        int idx = max_element(v.begin(),v.end())-v.begin();
        int l=0,r=0;
        if(idx-1>=0) l=v[idx-1];
        if(idx+1<v.size()) r=v[idx+1];
        ans+=v[idx]-max(l,r);
        vector<int> tmp;
        for(auto c : v){
            if(c!=v[idx]) tmp.push_back(c);
        }
        v=tmp;
    }
    printf("%d",ans);
}

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

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

[난이도] Gold1
[유형] Greedy

[풀이]
나중에..

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
int N,K;
ll v[4];
priority_queue<int> pq[4];
struct P{
    int idx,l;
};
bool cmp(P& a,P& b){
    return (a.l+v[a.idx])*v[b.idx] > (b.l+v[b.idx])*v[a.idx];
}
int main(){
    scanf("%d%d",&N,&K);
    for(int i=0;i<4;i++) scanf("%d",&v[i]);
    while(N--){
        char c;
        int l;
        scanf(" %c %d",&c,&l);
        pq[c-'A'].push(l);
    }
    while(K--){
        vector<P> t;
        for(int i=0;i<4;i++){
            if(pq[i].empty()) continue;
            t.push_back({i,pq[i].top()});
        }
        sort(t.begin(),t.end(),cmp);
        auto [idx,l] = t[0];
        pq[idx].pop();
        v[idx]+=l;
        printf("%c %d\n",idx+'A',l);
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold1/초직사각형.cpp

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

[난이도] Silver3
[유형] Greedy

[풀이]
P인 점을 기준으로 i-K~i+K 만큼을 확인하여 햄버거가 있으면 그 햄버거를 invalid 처리하고
정답에 1을 추가해주면 됩니다.

#include <iostream>
#include <string>
using namespace std;
int N,K,ans;
string s;
int main(){
    cin >> N >> K >> s;
    for(int i=0;i<N;i++){
        if(s[i]=='P'){
            for(int j=i-K;j<=i+K && j<N;j++){
                if(j<0) continue;
                if(s[j]=='H'){
                    ans++;
                    s[j]='O';
                    break;
                }
            }
        }
    }
    printf("%d",ans);
}

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

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

[난이도] Silver5
[유형] Greedy

[풀이]
N을 1,2,3...,K 와 같이 등차수열 형태로 할당이 가능한 경우는 답이 K-1로 최적인 경우입니다.

1~K의 합인 K(K+1)/2 보다 N이 큰 경우에는
큰 수부터 1을 할당해주면 됩니다.
예를 들어
N이 13이고 K가 4일 때,
1,2,3,4 -> 10개를 사용했고 3개가 남았습니다.
1,3,4,5 -> 3개를 큰 수부터 차례로 1씩 할당하여 답은 K = 4입니다.

만약 K가 15라면
2,3,4,5 로 할당 하는 것이 가능하여 답은 K-1 = 3이 됩니다.

이와 같이 N-K(K+1)/2 가 K로 나누어 떨어지는 경에 답은 K-1이 되고,
아닌 경우에는 가장 큰 값에 1을 무조건 더해주어야 하므로 답은 K가 됩니다.

#include <cstdio>
using namespace std;
int N,K,ans;
int main(){
    scanf("%d%d",&N,&K);
    int sum=K*(K+1)/2;
    if(sum>N){
        puts("-1");
        return 0;
    }
    int a = N-sum;
    if(a%K) printf("%d",K);
    else printf("%d",K-1);
}

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

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

[난이도] Silver1
[유형] Greedy

[풀이]
최종 볼의 상태는 모든 B가 왼쪽, 모든R이 오른쪽인 상태이거나,
R이 왼쪽, 모든 B가 오른쪽인 상태 둘중에 하나입니다.

각 케이스에서 해당 상태를 만드는 경우에는 R을 움직이는 경우, B를 움직이는 경우 두가지가 있습니다.
결국 총 4가지 케이스인데 이것을 각각 해보면 됩니다.

예를 들어 (B~)(R~) 상태를 R을 움직여서 만들려면 이미 오른쪽 끝에 있는 R들을 제외하고 나머지 R들을
1회 움직여서 오른쪽에 붙혀줘야 합니다.
즉 오른쪽 끝에 있는 R을 제외한 모든 R의 개수를 세주면 됩니다.

위 과정을 4가지 케이스에 대해 각각 해줘서 그중 최솟값을 답으로 출력해주면 됩니다.
여러가지 방법이 있겠지만 저는
이미 뭉쳐있는 공들을 pair vector를 이용해 하나의 묶음으로 묶어주었습니다.
예를 들어 RRBRRRBRRRR 이 있을 때,
{ {'R',2} , {'B',1} , {'R',3} , {'B',1} , {'R',4} } 와 같이 vector에 저장하면
모든 R을 오른쪽으로 보낼 때, index의 마지막인 {'R',4}는 무시하고 {'R',2}, {'R',3} 만 오른쪽으로 보내면 되므로
총 5번의 이동이 필요하게 됩니다.

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<pair<char,int>> v; 
int N;
string s;
int main(){
    cin >> N >> s;
    for(int i=0;i<s.size();i++){
        int j=i;
        int cnt=0;
        for(;j<s.size();j++){
            if(s[i]==s[j]) cnt++;
            else break;
        }
        v.push_back({s[i],cnt});
        i=j-1;
    }
    int ans,rtmp=0,btmp=0;
    for(int i=1;i<v.size();i++){
        auto [col,cnt] = v[i];
        if(col=='R') rtmp+=cnt;
        else btmp+=cnt;
    }
    ans=min(rtmp,btmp);
    rtmp=0,btmp=0;
    for(int i=v.size()-2;i>=0;i--){
        auto [col,cnt] = v[i];
        if(col=='R') rtmp+=cnt;
        else btmp+=cnt;
    }
    ans=min(ans,btmp);
    ans=min(ans,rtmp);
    printf("%d",ans);
}

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

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

[난이도] Gold5
[유형] Greedy

[풀이]
모든 강의의 시작 시간과 종료 시간을 동일한 vector<pair<int,int>>에 저장합니다.
시작 시간의 경우 +1을, 종료 시간은 -1을 묶어서 pair의 second에 저장해줍니다.
그 뒤 시간으로 정렬을 해준 뒤 second를 cur 변수에 더해주면서 이것의 최댓값을 갱신해주면 이것이 정답이 됩니다.
그 이유는 어떤 강의가 시작될때 1을 더해주고 끝날 때 1을 빼주게 되므로
동시에 진행중인 강의의 수가 cur에 저장되게 되기 때문입니다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
struct P{
    int s,e;
};
int N,ans;
vector<pair<int,int>> a;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        int t,s,e;
        scanf("%d%d%d",&t,&s,&e);
        a.push_back({s,1});
        a.push_back({e,-1});
    }
    sort(a.begin(),a.end());
    int cur=0;
    for(auto [v,m] : a){
        cur+=m;
        ans=max(cur,ans);
    }
    printf("%d",ans);
}

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

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

[난이도] Gold5
[유형] Greedy

[풀이]
O(N)에 0~N-1을 한번씩만 확인하면서 문제를 해결할 수 있습니다.
a[h] : 현재까지 a[h]에 위치하는 화살의 개수

현재 입력으로 v가 들어왔다면 a[v+1]을 확인해서 1 이상이면 v+1 위치에 화살이 내려와서
v의 풍선을 제거할 수 있습니다.
만약 a[v+1]이 0이라면 v 위치의 풍선을 제거할 풍선이 없으므로 v 높이로 화살을 날려야 하므로
정답에 1을 추가해줍니다.

#include <cstdio>
using namespace std;
int N,ans,a[1000001];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        int v;
        scanf("%d",&v);
        if(a[v+1]){
            a[v+1]--;
            a[v]++;
        }else{
            ans++;
            a[v]++;
        }
    }
    printf("%d",ans);
}

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