프로그래밍

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

[난이도] Gold2
[유형] Greedy

[풀이]
문제들 중에 데드라인이 최대인 문제의 데드라인이 M일 때,
M+1시간부터는 모든 문제의 데드라인이 종료되므로 문제를 풀 수 없습니다.
결국 1,2,3...M 시간에 각각 최대 1문제를 풀 수 있고 각 시간에 컵라면을 최대로 하기에 유리한 문제를 풀어야 합니다.

Greedy 알고리즘을 이용해야 하는데
M,M-1,M-2...1 과 같이 풀어야 하는 문제를 거꾸로 구해주면 쉽게 해결이 가능합니다.

1) 각 문제를 데드라인 순서로 정렬
2) i를 M~1 순서로 순회하면서 i보다 크거나 같은 데드라인을 가진 문제들의 컵라면 수를 우선순위 큐에 push
3) i시간에 풀 수 있는 문제는 과정 2)에 의해 모두 우선순위 큐에 들어있으므로 큐의 top이 결국 i시간에 선택할 수 있는    최적의 문제이므로 컵라면의 수를 ans에 더해줌

위의 과정을 반복하면서 누적된 ans 값이 최종 정답입니다.

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int N,M;
pair<int,int> a[200000];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        scanf("%d%d",&a[i].first,&a[i].second);
        M=max(M,a[i].first);
    }
    int ans=0;
    sort(a,a+N);
    priority_queue<int> pq;
    int j=N-1;
    for(int i=M;i>=1;i--){
        for(;j>=0&&a[j].first>=i;j--) pq.push(a[j].second);
        if(!pq.empty()) {
            ans+=pq.top();
            pq.pop();
        }
    }
    printf("%d",ans);
}

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

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

[난이도] Gold2
[유형] Greedy

[풀이]
우선 배열에 현재 (현재 탭 개수 - 목표 탭 개수) 를 저장해줍니다.
배열에서 양수인 것들은 탭을 빼줘야 하는 것들이고
음수인 것들은 탭을 더해주야 하는 것들입니다.

잘 생각해보면 부호가 같은 연속된 수열에서 절댓값이 가장 작은 값만큼 탭을 제거하거나 추가하는
연산을 하는게 가장 효율적인 연산입니다.

전체 수열이 0이 될때까지 루프를 돌면서 수열 전체를 확인하면서 위의 방법으로 탭을 추가하거나 제거해주면 됩니다.

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int N,a[1001];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    for(int i=0;i<N;i++) {
        int v;
        scanf("%d",&v);
        a[i]-=v;
    }
    int ans=0;
    bool ok=1;
    while(ok){
        ok=0;
        for(int i=0;i<N;i++){
            if(!a[i]) continue;
            ok=1;
            int minv=a[i];
            for(int j=i+1;j<=N;j++){
                if(a[i]*a[j]>0){
                    if(abs(a[j])<abs(minv)){
                        minv=a[j];
                    }
                }else{
                    ans+=abs(minv);
                    for(int k=i;k<j;k++) a[k]-=minv;     
                    i=j-1;
                    break;
                }
            }
        }
    }
    printf("%d",ans);
}

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

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

[난이도] Gold4
[유형] Greedy

[풀이]
거리의 합이 최소가 될때 유리하게 만들기 위해서는

우체국의 위치를 x라고 했을 때, x에 마을이 많을수록,
x를 기준으로 좌우에 퍼져있는 우체국의 수가 비슷할수록 유리합니다.

결국 마을위 위치를 기준으로 정렬한 뒤,
1~N 마을을 순회하면서 사람 수를 cur에 더해나갑니다.
그러다 cur>=(sum(전체 사람 수)+1)/2 를 만족하는 순간의 i가 우체국이 설치되었을 때
가장 유리한 마을의 index입니다.

#include <cstdio>
#include <algorithm>
using namespace std;
using ll = long long;
int N;
pair<ll,ll> xa[100001];

int main(){
    scanf("%d",&N);
    ll sum=0;
    for(int i=1;i<=N;i++) {
        scanf("%lld%lld",&xa[i].first,&xa[i].second);
        sum+=xa[i].second;
    }
    sort(xa+1,xa+N+1);

    ll cur=0;
    for(int i=1;i<=N;i++){
        cur+=xa[i].second;
        if(cur>=(sum+1)/2) {
            printf("%d",xa[i].first);
            break;
        }
    }
}

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

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

[난이도] Gold5
[유형] Greedy

[풀이]
K개의 조로 나눈다는 것을 결국 K-1개의 경계를 골라야 한다는 의미입니다.
키가 작은 순서로 0번부터 N-1번 원생이 서있다면,
경계를 나누지 않을 경우의 비용은 a[N-1]-a[0] 입니다. (a[i] : i번 원생의 키)
만약 i와 i-1 사이에 경계를 추가한다면 a[i]-a[i-1] 만큼은 비용에서 제외됩니다.
결국 K개의 조로 나눴을 때 가장 비용을 적게 하려면
K-1의 경계 중 가장 비용이 큰 경계를 고르면 됩니다.
a[i]-a[i-1] (i:1~N-1) 의 값을 배열에 저장한 뒤, 정렬하여 K-1개의 큰 비용을 구해서
전체 비용에서 빼주면 쉽게 구할 수 있습니다.

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

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

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

[난이도] Gold5
[유형] Greedy

[풀이]
음수인 좌표와 양수인 좌표를 각각 a,b vector에 저장한 뒤 따로 생각해줍니다.
가까운 위치에 있는 좌표부터 M개씩 책을 가져다 놓으면 됩니다.
만약 vector의 크기가 아래와 같이 M으로 나누어 떨어지지 않는다면
아래와 같이 5%2 = 1 번째 책부터 옮겨주면 됩니다.
왜냐하면 가까운 곳을 먼저 왕복해 주는것이 유리하기 때문입니다.

(M==2)
0      0+M     0+2M
-6 -28 -29 -37 -39

위와 같이 옮기면 6*2+29*2+39*2 = 158 이 됩니다.

  M
2 11
좌표가 양수인 크기 2 벡터는 위와 같이 M번째만 방문하면 두 책을 모두 옮길 수 있으므로
11*2=22 이 됩니다.

여기서 마지막으로 책을 가져놓은 좌표에서 다시 0으로 돌아오지 않아도 되므로
0에서 가장 먼 좌표가 포함되어 있는 음수 vector를 나중에 처리하는 것이 유리합니다.
그러므로 -39 좌표의 책을 옮긴 뒤에 0으로 돌아오는 것은 고려하지 않아도 되므로
158+22-39 = 131이 최종 정답이 됩니다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N,M;
vector<int> a,b;
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++) {
        int v;
        scanf("%d",&v);
        if(v>0) a.push_back(v);
        else b.push_back(-v);
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    int ans=0;
    if(!a.empty()){
        for(int i=a.size()%M-1;i<(int)a.size();i+=M){
            if(i>=0) ans+=a[i]*2;
        }
    }
    if(!b.empty()){
        for(int i=b.size()%M-1;i<(int)b.size();i+=M){
            if(i>=0) ans+=b[i]*2;
        }
    }
    if(a.empty()) ans-=b.back();
    else if(b.empty() || a.back()>b.back()) ans-=a.back();
    else ans-=b.back();

    printf("%d",ans);
}

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

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

[난이도] Gold4
[유형] Greedy

[풀이]
3이 최대만 많이 되도록
3^k , 3^k*2, 3^k*4 의 형태로 만들어 주면 가장 큰 수를 만들 수 있습니다.
즉 3으로 나눴을 때 나머지가 1이면  3^k*4의 형태로, 나머지가 2이면 3^k*2로 만들어 주면 됩니다.

예제5번의 답이 3^k * 4의 형태라 여기서 힌트를 얻었지만 수학적으로 왜 그렇게 되는지는 분석이 필요할 것 같습니다.

#include <cstdio>
using namespace std;
int N,mod=10007;
int main(){
    scanf("%d",&N);
    if(N==0){
        puts("0");
        return 0;
    }

    int k = N/3;
    int m = N%3;
    int ret=1;
    if(m==1) {
        if(k>0) {
            k--;
            ret=4;
        }
    }else if(m==2){
        ret=2;
    }

    for(int i=0;i<k;i++) ret=(ret*3)%mod;
    printf("%d",ret); 
}

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

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

[난이도] Gold4
[유형] Greedy

[풀이]
방 번호를 가장 크게 만드려면, 방 번호 숫자의 길이를 가장 길게 만들어야 하며,
그 뒤 가장 큰 자리수의 수들을 큰 수, 즉 N-1과 가까운 수로 만들수록 유리합니다.

이런 수를 만들기 위해 vector<pair<가격,숫자>> p 를 만들고 입력받은 값을 저장해준 뒤
정렬해주어 가격이 싼 것이 앞으로 오도록 합니다.
p[0]가 가장 싼 숫자가 되며, 주어진 돈 M을 이용해  이 숫자를 최대한 많이 사면
숫자를 가장 많이 살 수 있기 때문에 방 번호를 가장 길게 만들 수 있습니다.
이렇게 p[0].second 숫자로만 이루어진 string ret을 만들어 놓고

남은 돈을 이용해 ret[0],ret[1],ret[2]..... 순으로 가능하면 N-1에 가까운 숫자로 바꿔주면
가장 큰 방번호를 만들 수 있습니다.

주의해야 할 것이 p[0].second가 0이라면 전체 숫자가 0이 되지 않도록 가장 앞 숫자를 p[1].second가 되도록
해주어야 합니다.

#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
int N,M,P[10];
vector<pair<int,int>> p;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        scanf("%d",&P[i]);
        p.push_back({P[i],i});
    }
    scanf("%d",&M);
    sort(p.begin(),p.end());
    string ret;
    if(N==1){
        puts("0");
        return 0;
    }
    if(p[0].second!=0){
        int cnt = M/p[0].first;
        for(int i=0;i<cnt;i++) ret+=to_string(p[0].second);
        M-=cnt*p[0].first;
    }else{
        int m = M - p[1].first;
        if(m<0) {
            puts("0");
            return 0;
        }
        ret+=to_string(p[1].second);
        int cnt = m/p[0].first;
        for(int i=0;i<cnt;i++) ret+=to_string(p[0].second);
        M=m-cnt*p[0].first;
    }
    for(int i=0;i<ret.size();i++){
        bool ok=0;
        int cur = P[ret[i]-'0'];
        for(int j=N-1;j>=0;j--){
            if(M-(P[j]-cur)>=0){
                M-=P[j]-cur;
                ok=1;
                ret[i]=j+'0';
            }
            if(ok) break;
        }
        if(!ok) break;
    }
    printf("%s",ret.c_str());
}

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

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

[난이도] Gold3
[유형] Greedy

[풀이]
학교를 기준으로 먼 쪽에 있는 아파트부터 방문하면서 학생을 태워오는 Greedy 방식을 이용하면
통학버스의 이동거리를 최소로 할 수 있습니다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int N,K,S,ans;
vector<pair<int,int>> apart[2];
int main(){
    scanf("%d%d%d",&N,&K,&S);
    for(int i=0;i<N;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        if(S>u) apart[0].push_back({u,v});
        else apart[1].push_back({u,v});
    }
    sort(apart[0].begin(),apart[0].end());
    sort(apart[1].begin(),apart[1].end());
    reverse(apart[1].begin(),apart[1].end());
    for(int k=0;k<2;k++){
        for(int i=0;i<apart[k].size();i++){
            int cur=0;
            for(int j=i;j<apart[k].size();j++){
                int t = cur + apart[k][j].second;
                if(t>=K){
                    apart[k][j].second = t - K;
                    cur=0;
                    ans+=2*abs(S-apart[k][i].first);
                    i=j;
                    if(t>K) i--;
                    break;
                }else{
                    cur+=apart[k][j].second;
                }
                if(j==apart[k].size()-1 && cur!=0){
                    ans+=2*abs(S-apart[k][i].first);
                    i=j;
                } 
            }
        }
    }
    printf("%d",ans);
}

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