프로그래밍

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

[난이도] Gold4
[유형] 플로이드 와샬

[풀이]
플로이드 와샬로 모든 지점간 거리를 구한 후
각 점에서 M거리 이하인 지점의 아이템 개수를 모두 더한 값의 최솟값이 정답이다.

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

#include <cstdio>
#include <algorithm>
using namespace std;
int N,M,R,item[101],dist[101][101],inf=9e8,ans;
int main(){
    scanf("%d%d%d",&N,&M,&R);
    for(int i=1;i<=N;i++) scanf("%d",&item[i]);
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(i!=j) dist[i][j] = inf;
        }
    }
    while(R--){
        int a,b,l;
        scanf("%d%d%d",&a,&b,&l);
        dist[a][b] = min(dist[a][b],l);
        dist[b][a] = min(dist[b][a],l);
    }

    for(int k=1;k<=N;k++)
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++) dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);

    for(int i=1;i<=N;i++){
        int sum=0;
        for(int j=1;j<=N;j++){
            if(dist[i][j]<=M) sum+=item[j];
        }
        ans = max(ans,sum);
    }
    printf("%d",ans);
}

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

[난이도] Gold4
[유형] BFS

[풀이]
visit배열의 값을 3가지로 사용한다. (0:불도 안켜진 상태 1:불만 켜진상태 2:방문완료한 상태)
(1,1)부터 BFS를 시작한다. 인접하고 불이 켜진 곳을 queue에 넣기 전에
현재 위치에서 킬 수 있는 불을 켜준다.
여기서 주의할 점이 방금 불을 켠 점의 인접한 곳에 (2:방문 완료한 상태)인 점이 있다면 이곳도
방문할 수 있는 점에 추가되어야 하기 때문에 queue에 넣어줘야 한다.

#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
int N,M,cnt,visit[102][102],dy[4]={-1,1,0,0},dx[4]={0,0,1,-1}; 
vector<pair<int,int>> adj[101][101];
int main(){
    scanf("%d%d",&N,&M);
    while(M--){
        int y,x,b,a;
        scanf("%d%d%d%d",&x,&y,&a,&b);
        adj[y][x].push_back({b,a});
    }
    queue<pair<int,int>> q;
    q.push({1,1});
    visit[1][1]=2;
    int cnt=1;
    while(!q.empty()){
        int qsz=q.size();
        auto f = q.front(); q.pop();
        int y = f.first, x=f.second;
        for(auto p : adj[y][x]){
            int ny = p.first, nx = p.second;
            if(!visit[ny][nx]){
                for(int i=0;i<4;i++){
                    int ty=ny+dy[i],tx=nx+dx[i];
                    if(visit[ty][tx]==2) {
                        q.push({ty,tx});
                        break;
                    }
                }
                visit[ny][nx]=1;
                cnt++;
            }
        }
        for(int i=0;i<4;i++){
            int ny = y+dy[i], nx= x+dx[i];
            if(visit[ny][nx]==1){
                visit[ny][nx]=2;
                q.push({ny,nx});
            }
        }
    }
    printf("%d",cnt);
}

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

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

[난이도] Gold4
[유형] DP

[풀이]
DP[cur][a][b] : cur구간까지 진행됬을 때 A는 a만큼 이기고, B는 b만큼 이겼을 때의 확률

DP[cur-1][..][..]의 값을 이용해서 모든 DP[cur][a][b]의 값을 구할 수 있다.

점화식 =>
DP[cur][a][b] = A*B*DP[cur-1][a-1][b-1] (A: A가 이길 확률, B: B가 이길 확률)
+ (1-A)*B*DP[cur-1][a][b-1]
+ A*(1-B)*DP[cur-1][a-1][b]
+ (1-B)*(1-A)*sol[cur-1][a][b]

#include <cstdio>
double A,B,dp[19][19][19];
int k[12] = {0,1,4,6,8,9,10,12,14,15,16,18};
double sol(int cur,int a,int b){
    if(cur<a || cur<b || a<0 || b<0) return 0;
    if(cur==0) return 1;
    
    double& ret = dp[cur][a][b];
    if(ret!=-1.0) return ret;
    ret=0.0;
    ret+=A*B*sol(cur-1,a-1,b-1);
    ret+=(1-A)*B*sol(cur-1,a,b-1);
    ret+=A*(1-B)*sol(cur-1,a-1,b);
    ret+=(1-B)*(1-A)*sol(cur-1,a,b);    
    return ret;
}
int main(){
    scanf("%lf%lf",&A,&B);
    A/=100,B/=100;
    for(int i=0;i<=18;i++)
        for(int j=0;j<=18;j++) 
            for(int k=0;k<=18;k++) dp[i][j][k]=-1.0;


    for(int i=0;i<=18;i++)
        for(int j=0;j<=18;j++) sol(18,i,j);
    
    double ans = 1;    
    for(int i=0;i<12;i++)
        for(int j=0;j<12;j++) ans-=dp[18][k[i]][k[j]];
        
    printf("%.7lf",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1344.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/1367/problem/A

[난이도] Div.3
[유형] 구현

[풀이]
맨 앞, 맨 뒷 글자는 무조건 출력해주고
가운데 글자들은 같은 글자가 두번씩 나오므로 한번씩만 출력되도록 하면 된다.

#include <string>
#include <iostream>
using namespace std;
int tc;
int main(){
    cin >> tc;
    while(tc--){
        string s;
        cin >> s;
        cout << s[0];
        for(int i=1;i<s.size()-1;i+=2) cout << s[i];
        cout << s.back();
        puts("");
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round650-Div.3/A.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