프로그래밍

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

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

[풀이]

배열을 전부 만들어봐야 하는지, DP로 풀어야하는지 등등 여러 삽질을 하다가
A번 문제인데도 컨테스트중에 풀지 못한 문제입니다. ㅠㅠ

tutorial을 보니 접근을 완전히 잘못 한것을 깨달았습니다.

n이 배열의 모든 원소의 합이라고 할때
n==1 -> [1] : 길이1
n==4 -> [1,3] : 길이2
n==9 -> [1,3,5] : 길이3
n==16 -> [1,3,5,7] : 길이4
...

위와같이 n이 1,2,3,4..의 제곱수이면 최소 배열의 길이가 1씩 늘어남을 알 수 있습니다. (2씩 큰수를 추가하면 되므로)

1 2개
4 3개
9 4개
각 배열의 마지막수를 1씩 감소시켜서 배열을 만들어보면
위와같이 n일때 최소 배열의 길이를 찾을 수 있습니다.

예를 들어 n==10일때를 구해본다면
[1,3,5,7]을 [1,3,5,1]로 바꿔주는 식으로 마지막 수를 1씩 줄여보면 모든 n에 대해서 구할 수 있습니다.

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

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

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

[풀이]
최대 100번의 연산 내에 A배열을 B배열로 만들어야 합니다.
각 루프에서 i:0~N-1 루프를 돌면서 A[i]-B[i]가 가장 작은 값과 큰 값을 찾아서 저장한 뒤
A[i]-B[i]가 작은 A[i]는 +1, 큰 A[i]는 -1 을 해주면
이것이 매 루프마다 정답에 가장 유리한 연산이 됩니다.

100번내에 A=B를 만들 수 있으면 정답을 출력합니다.

#include <cstdio>
#include <queue>
#include <cstring>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int tc,N,a[100],b[100],INF=987654321;

bool same(){
    for(int i=0;i<N;i++){
        if(a[i]!=b[i]) return false;
    }
    return true;
}
void prt(){
    for(int i=0;i<N;i++){
        printf("%d ",a[i]);
    }
    puts("");
}
void solve(){

    int it=100;
    vector<pair<int,int>> ans;
    while(it--){

        int minDiff=INF,minIdx=-1;
        int maxDiff=-INF,maxIdx=-1;
        bool ok=1;
        for(int i=0;i<N;i++){
            int d = a[i]-b[i];
            if(d!=0) ok=0;
            if(minDiff>d){
                minDiff=d;
                minIdx=i;
            }
            if(maxDiff<d){
                maxDiff=d;
                maxIdx=i;
            }
        }
        if(ok) break;

        a[minIdx]++;
        a[maxIdx]--;
        ans.push_back({maxIdx,minIdx});
    }
    if(same()){
        printf("%d\n",ans.size());
        for(auto p : ans){
            printf("%d %d\n",p.first+1,p.second+1);
        }
    }else{
        puts("-1");
    }
}

int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&N);
        for(int i=0;i<N;i++) scanf("%d",&a[i]);
        for(int i=0;i<N;i++) scanf("%d",&b[i]);
        solve();
    }
}

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

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

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

[풀이]
Greedy 문제입니다.

a,b 배열의 index를 aidx, bidx로 유지하면서 a[aidx],b[bidx]중 하나를 선택해
ans vector에 추가해주는 식으로 풉니다. 정답이 존재한다면 ans vector의 크기가 n+m이 되어야 합니다.

a[adix],b[bidx] 중에 고르는 기준은 다음과 같습니다..
1) 둘중 0이 있는 경우 무조건 선택한다. 새로운 라인을 추가하는 것은 어떤 경우에도 유리하기 때문
2) 0이 없을때는 k (현재 페이지의 총 라인수) 보다 작거나 같은 값이 있으면 선택한다. 라인을 수정하는 것은
아직 선택되지 않은 것들에 어떤 악영향도 미치지 않으므로

aidx==n , bidx==m이 될때까지 위 과정을 반복하면 ans vector에 최종 정답이 저장됩니다.

#include <cstdio>
#include <queue>
#include <cstring>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int tc;
int k,n,m,a[301],b[301];
 
void prt(){
    puts("a");
    for(int i=0;i<n;i++) printf("%d ",a[i]);
 
    puts("b");
    for(int i=0;i<m;i++) printf("%d ",b[i]);
}
 
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d%d%d",&k,&n,&m);
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        for(int i=0;i<m;i++) scanf("%d",&b[i]);
        vector<int> ans;
 
        int aidx=0,bidx=0;
        int it=m+n;
        while(it--){
            if(aidx<n){
                if(a[aidx]==0) {
                    k++;
                    aidx++;
                    ans.push_back(0);
                    continue;
                }
            }
            if(bidx<m){
                if(b[bidx]==0) {
                    k++;
                    bidx++;
                    ans.push_back(0);
                    continue;
                }
            }
 
            if(aidx<n){               
                if(k>=a[aidx]){
                    ans.push_back(a[aidx]);
                    aidx++;
 
                    continue;
                }
            }            
            if(bidx<m){
                if(k>=b[bidx]){
                    ans.push_back(b[bidx]);
                    bidx++;
                    continue;
                }
            }    
        }
        if(ans.size()<m+n) puts("-1");
        else{
            for(int a : ans) printf("%d ",a);
            puts("");
        }
    }
    
}

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

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

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

[풀이]
'a'의 index를 찾고 왼쪽 index l 오른쪽 index r을 유지하면서
'b','c','d'..가 순서대로 l,r 둘중 하나에 존재하는지를 체크해줍니다.
만약 지금 나와야하는 알파벳이 l,r 둘중 하나에 없다면 NO를 출력해주고,
모든 알파벳을 찾을 수 있다면 YES를 출력합니다.

#include <cstdio>
#include <queue>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

int tc;
string s;

bool solve(){
    int cur=-1;
    for(int i=0;i<s.size();i++){
        if(s[i]=='a') {
            cur=i;
            break;
        }
    }
    if(cur==-1) return false;
    int l=cur,r=cur;

    int sz = s.size()-1;
    char target='b';
    while(sz--){

        if(l-1>=0){
            if(s[l-1]==target){
                l--;
                target++;
                continue;
            }
        }
        if(r+1<s.size()){
            if(s[r+1]==target){
                r++;
                target++;
                continue;
            }
        }
        return false;
    }
    return true;
}
int main(){
    scanf("%d",&tc);
    while(tc--){
        cin >> s;
        string ret = solve()?"YES":"NO";
        cout << ret << '\n';
    }

}

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

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

[난이도] Gold5
[유형] Greedy

[풀이]
N개의 센서를 위치 기준으로 정렬한 뒤, 센서들 사이의 거리 N-1개를 배열에 넣은 후 다시 정렬을 해준다.
그 뒤 거리가 큰 K-1개의 거리를 뽑아서 그 구간을 제거하면 총 K개의 집중국을 설치한 것과 같은 효과를 가진다.
그러므로 뽑은 K-1개의 거리들을 총 구간에서 빼주면 정답이 된다.

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

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

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

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

[풀이]
a[1]과 a[N]에 어떤 수가 들어있는지에 따라서 답을 구해야 한다.

최악의 경우는
a[1]에 N, a[N]에 1이 있는 경우, 이 경우에는 1~N-1을 sort -> 2~N을 sorting -> 1~N-1을 sorting 총 3번을 sorting 해야 한다.

이미 정렬이 되어있는 경우 0번

a[1]==1 이거나 a[N]==N인 경우 이것을 제외하고 1번만 정렬하면 되므로 1번

나머지 경우는 2번만 정렬해주면 된다.

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
using namespace std;
using ll = long long;
 
int t,N,a[51];
 
int solve(){
    bool ok=1;
    for(int i=1;i<=N;i++){
        if(a[i]!=i){
            ok=0;
            break;
        }
    }
    if(ok) return 0;
    
    if(a[1]==1 || a[N]==N) return 1;
    if(a[1]==N && a[N]==1) return 3;
 
    return 2;
}
 
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&N);
        for(int i=1;i<=N;i++) scanf("%d",&a[i]);
        printf("%d\n",solve());
    }
}

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

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

[난이도] Gold5
[유형] Greedy

[풀이]
크레인의 용량과 박스의 크기를 내림차순을 해준 뒤
1번의 사이클에서 가장 들 수 있는 무게가 큰 크레인부터 가장 큰 박스를 매칭시켜주면 된다.
만약 박스가 선택되었으면 erase 연산으로 vector에서 지워주면서 반복한다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N,M;
vector<int> a,b;
bool cmp(int a,int b){
    return a>b;
}
int main(){
    scanf("%d",&N);
    a.resize(N);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    scanf("%d",&M);
    b.resize(M);
    for(int i=0;i<M;i++) scanf("%d",&b[i]);

    sort(a.begin(),a.end(),cmp);
    sort(b.begin(),b.end(),cmp);
    if(a[0]<b[0]) {
        puts("-1");
        return 0;
    }
    int ans =0;
    while(b.size()!=0){
        for(int i=0;i<a.size();i++){
            for(int j=0;j<b.size();j++){
                if(a[i]>=b[j]){
                    b.erase(b.begin()+j);
                    break;
                }
            }
        }
        ans++;
    }
    printf("%d",ans);
}

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

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

[난이도] Gold3
[유형] Greedy

[풀이]
0(A)~9(J)을 저장할 수 있는 배열을 만들고 각 문자열마다 문자열을 1자리수부터 확인하면서
해당 알파벳의 해당하는 배열값에 10^자릿수 만큼을 더해준다.
그 뒤 배열값이 큰 인덱스에 해당하는 알파벳부터 9,8,7... 순서로 할당하면
가장 큰 합을 구할 수가 있다.
이 때, 맨 앞자는 0이 되면 안되므로 맨 앞에 0이 오는 알파벳에는 0을 할당하지 않도록
예외처리를 해준다.

#include <iostream>
#include <string>
#include <algorithm>
using ll = long long;
using namespace std;
int N,t[10];
ll v[10];
bool isF[10];
string a[50];
pair<ll,int> b[10];
int main(){
    cin >> N;
    for(int i=0;i<N;i++) cin >> a[i];
    for(int i=0;i<N;i++){
        string s = a[i];
        ll k=1;
        for(int j=s.size()-1;j>=0;j--){
            v[s[j]-'A']+=k;
            k*=10;
        }
    }
    for(int i=0;i<N;i++) isF[a[i][0]-'A']=1;

    for(int i=0;i<10;i++) b[i]={v[i],i};
    sort(b,b+10);

    if(b[0].first!=0 && isF[b[0].second]){
        int idx=1;
        for(;;idx++) if(!isF[b[idx].second]) break;
        auto tmp = b[idx];
        for(int i=idx-1;i>=0;i--) b[i+1]=b[i];
        b[0]=tmp;
    }

    for(int i=9,j=9;i>=0;i--,j--){
        if(b[i].first==0) break;
        t[b[i].second]=j;
    }
    ll ans = 0;
    
    for(int i=0;i<N;i++){
        string s = a[i],ret;
        for(int j=0;j<s.size();j++) ret+=t[s[j]-'A']+'0';
        ans+=stoll(ret);
    }
    cout << ans;
}

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