프로그래밍

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

[난이도] Gold4
[유형] BFS

[풀이]
전형적인 BFS 문제이다.

#include <cstdio>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;
const int mxN=1e5;
int N,T,G;
bool visit[mxN];
int main(){
    scanf("%d%d%d",&N,&T,&G);
    queue<int> q;
    q.push(N);
    visit[N]=1;

    int cnt = 0;
    while(!q.empty()){
        int sz = q.size();
        while(sz--){
            int qf = q.front(); q.pop();
            if(qf==G) {
                printf("%d",cnt);
                return 0;
            }
            if(qf+1<mxN){
                if(!visit[qf+1]) {
                    visit[qf+1]=1;
                    q.push(qf+1);
                }
            }
            if(qf*2<mxN){
                int t=0;
                if(qf*2!=0){
                    string a = to_string(qf*2);
                    a[0]--;
                    t = stoi(a);
                }
                if(!visit[t]){
                    visit[t]=1;
                    q.push(t);
                }
            }
        }
        cnt++;
        if(cnt>T) break;
    }
    puts("ANG");
}

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

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

[난이도] Gold4
[유형] DP

[풀이]
전형적인 DP 문제

DP(n,k): 현재 k시간을 썼고 n번 길을 지나야 할때 얻을 수 있는 최대 모금액
점화식 => DP(n,k) =max( DP(n+1,k+[n번째 도보 시간])+[n번째 도보 모금액] ,
DP(n+1,k+[n번째 자전거 시간])+[n번째 자전거 모금액] )

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int N,K,pt[100][2],pr[100][2],dp[100][100001];
int sol(int n,int k){
    if(k>K) return -9e8;
    if(n==N) return 0;
    int& ret = dp[n][k];
    if(ret!=-1) return ret;
    ret = max(sol(n+1,k+pt[n][0])+pr[n][0],sol(n+1,k+pt[n][1])+pr[n][1]);
    return ret;
}
int main(){
    scanf("%d%d",&N,&K);
    for(int i=0;i<N;i++) scanf("%d%d%d%d",&pt[i][0],&pr[i][0],&pt[i][1],&pr[i][1]);
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0,0));
}

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

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

[난이도] Gold4
[유형] LCA

[풀이]
1. 공통 조상을 찾아야 하는 두 노드의 깊이를 구한다.
2. 깊이가 더 깊은 노드를 깊이 차이만큼 부모로 보내 깊이를 맞춰준다.
3. 깊이가 같아진 두 노드를 부모로 보내는 것을 반복하면서 두 노드가 같아지면
그 노드가 공통 조상이다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int tc,N,par[10001],rt,p1,p2;
int getH(int n){
    int ret=0,cur=n;
    while(cur!=rt){
        cur=par[cur];
        ret++;
    }
    return ret;
}
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&N);
        memset(par,0,sizeof(par));
        for(int i=1;i<N;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            par[b]=a;
        }
        scanf("%d%d",&p1,&p2);
        for(int i=1;i<=N;i++){
            if(par[i]==0) {
                rt=i;
                break;
            }
        }
        int p1h=getH(p1),p2h=getH(p2);
        if(p1h<p2h) {
            swap(p1,p2);
            swap(p1h,p2h);
        }
        for(int i=0;i<p1h-p2h;i++) p1=par[p1];
        while(p1!=p2){
            p1=par[p1];
            p2=par[p2];
        }
        printf("%d\n",p1);
    }
}

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

https://codeforces.com/contest/1409

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

[풀이]
axb가 작아지려면 a와 b의 차이가 크게 날수록 작아진다.
n을 a에서 먼저 뺄수 있을 만큼 빼주고 b에서 뺄 수 있을 만큼 빼준값과
n을 b에서 먼저 뺄수 있을 만큼 빼주고 a에서 뺄 수 있을 만큼 빼준값을
비교해서 더 작은 값을 정답으로 하면 된다.

#include <cstdio>
#include <algorithm>
using namespace std;
using ll = long long;
int tc; 
ll a,b,x,y,n,ret;
ll sol(){
    ll ans,tn;
    if(a-x>=n){
        ans = (a-n)*b;
    }else{
        tn = n-(a-x);
        ans = x*max(y,b-tn);
    }
    return ans;
}
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d%d%d%d%d",&a,&b,&x,&y,&n);
        ret = sol();
        swap(a,b);
        swap(x,y);
        ret = min(ret,sol());
        printf("%lld\n",ret);
    }
}

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

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

[난이도] Div.3
[유형] 수학

[풀이]
a,b 차이의 절댓값을 d라고 했을 때 d/10의 값에다 d%10이 0이 아니라면 1을 더한 값을 출력해주면 된다.

#include <cstdio>
#include <cmath>
using namespace std;
int tc,a,b;
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d%d",&a,&b);
        int d = abs(a-b);
        printf("%d\n",d/10+(d%10!=0));
    }
}

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

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

[난이도] Gold4
[유형] 구현

[풀이]
그냥 구현하면 시간초과가 난다. (1000000*700*2=14억) 의 연산이 필요
=> 최적화가 필요하다.
1. 0,1,2 성장중에서 가장 비중을 많이 차지하는 성장치(a)를 구함
2. 모든 날에 그 a만큼 성장한다고 가정하고 그 모든날에 a만큼 더해줌.
3. 실제로 N개의 입력을 재순회 사면서 성장치가 a인 경우는 스킵하고 a가 아닌 경우에는
그 값으로 수정하는 보정값을 더해준다.
(이 과정으로 시간을 줄이기 때문에 가장 비중을 많이 차지하는 성장치 a를 골랐다. 그 비중만큼 스킵이 가능하기 때문에. 적어도 1/3만큼은 스킵이 가능하다.)
4. 왼쪽열과 행의 최종 값이 업데이트 되었으므로 M*M 배열을 채워준다.

※ 가장 많은 가중치를 구하지 않고 무조건 0을 스킵하는 방식으로 해도 AC를 받을 수 있다고 한다.
※ 누적합 개념을 이용하면 O(N) 의 시간으로 해결이 가능하다. (이게 정해인듯함. 위의 풀이는 O((2*M)/3*N))

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N,M,map[700][700],t[1400],a[1000000][3],mi;
pair<int,int> cnt[3];
int main(){
    scanf("%d%d",&N,&M);
    
    for(int i=0;i<M;i++){
        for(int j=0;j<3;j++){
            int v;
            scanf("%d",&v);
            cnt[j].second=j;
            cnt[j].first+=v;
            a[i][j]=v;
        }
    }
    sort(cnt,cnt+3);
    mi = cnt[2].second;
    for(int i=0;i<2*N;i++) t[i]=mi*M;

    for(int i=0;i<M;i++){
        int k=0;
        for(int j=0;j<3;j++){
            int s=k,e=k+a[i][j];
            if(j!=mi){
               for(int l=s;l<e;l++){
                   t[l]+=(j-mi);
               } 
            }
            k=e;
        }
    }
    int j=0;
    for(int i=N-1;i>=0;i--) map[i][0] = t[j++];
    for(int i=1;i<N;i++) map[0][i] = t[j++];

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(i&&j) map[i][j] = max(map[i-1][j-1],max(map[i-1][j],map[i][j-1]));
            printf("%d ",map[i][j]+1);
        }
        puts("");
    }
}

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

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

[난이도] Gold4
[유형] 플로이드 워셜

[풀이]
각 집하장간 최단거리는 플로이드 워셜 알고리즘으로 구할 수 있다.
이 문제에서는 플로이드로 i,j의 최단 경로를 구했을 때, i다음 가야하는
집하장을 구해야한다. 이것을 path[i][j]에 저장한다.
경로를 갱신할 때 다음 중간에 거쳐가야할 집하장을 k라고 하면
path[i][j] = path[i][k]로 갱신하여 모든 i,j 쌍에 대해 path[i][j]를 구할 수 있다.

#include <cstdio>
int N,M,dist[201][201],inf=9e8,path[201][201];
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) {
            dist[i][j]=inf;
            if(i==j) dist[i][j]=0;
        }
    while(M--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        dist[a][b]=dist[b][a]=c;
        path[a][b]=b;
        path[b][a]=a;
    }
    for(int k=1;k<=N;k++)
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++) {
                if(dist[i][j] > dist[i][k]+dist[k][j]){
                   dist[i][j] = dist[i][k]+dist[k][j];
                   if(i!=k) path[i][j] = path[i][k];
                }
            }    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++) {
            if(path[i][j]) printf("%d ",path[i][j]);
            else printf("%c ",'-');
        }        
        puts("");
    }
}

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

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

[난이도] Gold4
[유형] 다익스트라, 플로이드 워셜

[풀이]
원래 길이 있는 경우에는 비용이 안드므로 0의 cost,
단방향 통행만 가능하면 그 반대로 오는길은 1의 cost를 준 뒤
다익스트라를 돌려주면 몇개의 단방향 길을 바꿔야 하는지 알 수 있다.
모든 쿼리마다 다익스트라를 돌리면 시간초과가 나므로 출발점 N개에 대해
한번씩만 호출되도록 한다.

(플로이드 워셜로 풀면 훨씬 간결하게 풀 수 있다.)

#include <algorithm>
#include <queue>
#include <cstring>
#include <vector>
#include <cstdio>
using namespace std;
int N,M,K,inf=9e8;
vector<pair<int,int>> adj[251];
int s,e,dist[251][251];
void dijk(){
    fill(dist[s],dist[s]+N+1,inf);
    priority_queue<pair<int,int>> pq;
    dist[s][s]=0;
    pq.push({0,s});
    while(!pq.empty()){
        auto qt = pq.top(); pq.pop();
        int cur = qt.second, cd=-qt.first;
        if(cd > dist[s][cur]) continue;
        for(auto next : adj[cur]){
            int nxt = next.first, nd = cd+next.second;
            if(dist[s][nxt] > nd){
                dist[s][nxt] = nd;
                pq.push({-nd,nxt});
            }
        }
    }
}
int main(){
    scanf("%d%d",&N,&M);
    while(M--){
        int u,v,k;
        scanf("%d%d%d",&u,&v,&k);
        adj[u].push_back({v,0});
        adj[v].push_back({u,!k});
    }
    scanf("%d",&K);
    memset(dist,-1,sizeof(dist));
    while(K--){
        scanf("%d%d",&s,&e);
        if(dist[s][s]==-1) dijk();
        printf("%d\n",dist[s][e]);
    }
}

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