프로그래밍

www.acmicpc.net/problem/2457  

[난이도] Gold4

[유형] Greedy

[풀이]

pair vector를 만들어서 first에 꽃이 피는날 second에 꽃이 지는날을 저장 후 정렬.

0~N-1 루프를 돌면서 최적의 꽃을 찾아주면 된다.

코드에서 s는 현재까지 꽃이 무조건 피어있다고 보장되는 날이다.

first가 s이하인 꽃들 중에서 second가 가장 큰 값을 mxr에 갱신해서 찾는다.

first가 s를 넘어가게 되면 위의 mxr이 최대인 꽃을 선택하고 다음 꽃을 찾는다.

이 때, 꽃이 피어있다고 보장되는나 s는 mxr로 갱신시킨다.

위의 과정을 반복하면 된다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int a[] = {0,31,28,31,30,31,30,31,31,30,31,30,31},base[13];
int N,ans;
vector<pair<int,int>> v;
int main(){
    for(int i=1;i<=12;i++) base[i]=a[i-1]+base[i-1];
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        int b[4];
        for(int j=0;j<4;j++) scanf("%d",&b[j]);
        v.push_back({base[b[0]]+b[1],base[b[2]]+b[3]});
    }
    sort(v.begin(),v.end());

    int s=base[3]+1,e=base[11]+30,mxr=-1,ok=0;
    for(int i=0;i<N;i++){
        auto p = v[i];
        int l=p.first,r=p.second;
        if(l<=s) {
            mxr=max(r,mxr);
            if(mxr > e){
                ok=1;
                ans++;
                break;
            }
        }
        else {
            if(mxr==-1) break;
            ans++;
            s=mxr;
            mxr=-1;
            i--;
        }
    }
    printf("%d",ok?ans:0);
}

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

www.acmicpc.net/problem/8980  

[난이도] Gold4

[유형] Greedy

[풀이]

어떤 마을에 도착했을 때 트럭에 실려있으면서 그마을이 목적지로 되어있는 택배는 모두 내리면 되므로

실을 때 어떻게 실어야 최적이 되는지만 생각하면 된다.

=> Greedy

=> 가장 빨리 내릴 수 있는 택배를 가장 많이 싣고 있는 것이 최적이다.

1. 각 마을에서 택배를 실을 때, 현재 택배를 실고있는 마을에서 가장 가까운 마을부터 택배를 싣는다.

   ex) 현재 마을이 i라면 목적지가 i+1 ~ N 순서로 택배를 차례로 싣는다.

2. 만약 i+1,i+2...j-1 번 마을이 도착지인 택배는 다실었는데 j번째를 싣다가 C를 초과하게 되면

   현재 최적이 되는 것을 방해하고 있는 택배들이 있는지 확인하고 그 택배들을 빼고 대신 j를 실어야 한다.

   제일먼저 빼야하는 택배(가장 비효율적인 택배) 들은 N 마을이 도착지인 택배들이다.

   => N~j+1 마을이 도착지인 택배들을 순서대로 확인하면서 있으면 그 택배들을 빼주고 j번 택배를 싣는다.

#include <cstdio>
#include <cstring>
int N,C,M,dest[2001][2001],cnt[2001],ans;
int main(){
    scanf("%d%d%d",&N,&C,&M);
    while(M--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        dest[a][b]=c;
    }
    int t = 0;
    for(int i=1;i<=N;i++){
        ans+=cnt[i];
        t-=cnt[i];
        for(int j=i+1;j<=N;j++){
            if(!dest[i][j]) continue;
            if(t+dest[i][j]<=C){
               cnt[j]+=dest[i][j];
               t+=dest[i][j];
            }else{
               cnt[j]+=C-t; 
               dest[i][j]-=C-t;
               t = C;               
               for(int k=N;k>j;k--){
                   if(!dest[i][j]) break;
                   if(cnt[k] > 0){
                       if(dest[i][j]<=cnt[k]){
                           cnt[j]+=dest[i][j];
                           cnt[k]-=dest[i][j];
                           dest[i][j]=0;
                       }else{
                           cnt[j]+=cnt[k];
                           dest[i][j]-=cnt[k];
                           cnt[k]=0;
                       }
                   }
               }
            }
        }
    }
    printf("%d",ans);
}

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

www.acmicpc.net/problem/1339

[난이도] Gold4

[유형] Greedy / 완전탐색

[풀이]

1. Greedy

모든 문자가 1이라고 가정하고 각 문자의 자리수를 고려한 총합이 최대가 되는 문자에 9부터 차례로 할당했을 때의 합을 출력한다.

2. 완전탐색

k가 총 문자 종류의 수일 때 9-k+1 ~ 9 의 문자를 각 문자에 할당할 수 있는 모든 경우의 수를 고려하면 된다. 10!이므로 시간초과나지 않는다. (stoi를 사용했을 경우에 시간초과가 났음)

#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
using namespace std;
int N,a[27],ans,cnt;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        string s;
        cin >> s;
        for(int j=0;j<s.size();j++){
            int sz = s.size()-j-1;
            int k = 1;
            while(sz--) k*=10;
            a[s[j]-'A'] += k;
        }
    }
    vector<int> v;
    for(int i=0;i<26;i++) if(a[i]) v.push_back(a[i]);
    sort(v.begin(),v.end());
    int j=0;
    for(int i=9-v.size()+1;i<=9;i++) ans += i*v[j++];
    cout << ans;
}


// #include <algorithm>
// #include <vector>
// #include <string>
// #include <iostream>
// #include <set>
// using namespace std;
// int N,cvt[27],ans;
// vector<string> a;
// int main(){
//     set<char> s;
//     scanf("%d",&N);
//     a.resize(N);
//     for(int i=0;i<N;i++){
//         cin >> a[i];
//         for(auto c : a[i]) s.insert(c);
//     }
//     vector<int> v;
//     for(int i=0;i<s.size();i++) v.push_back(9-i);
//     reverse(v.begin(),v.end());
//     do{ 
//         int i=0;
//         for(auto c : s) {
//             cvt[c-'A']=v[i++];
//         }
//         int sum = 0;
//         for(auto str : a){
//             int k=1;
//             for(int j=str.size()-1;j>=0;j--) {
//                 sum+=cvt[str[j]-'A']*k;
//                 k*=10;
//             }
//         }
//         ans = max(ans,sum);
//     }while(next_permutation(v.begin(),v.end()));
//     cout << ans;
// }

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1339.cpp

https://programmers.co.kr/learn/courses/30/lessons/42883

[풀이] Greedy

Upperbound를 이용해서 고를 수 있는 범위 내에서 9~0까지 for문을 돌면서 가장 먼저 선택할 수 있는

값을 하나씩 고르면 된다.

https://github.com/has2/Algorithm/blob/master/programmers/level2/%ED%81%B0%20%EC%88%98%20%EB%A7%8C%EB%93%A4%EA%B8%B0.cpp