프로그래밍

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

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

[난이도] Gold4
[유형] 재귀

[풀이]
2차원 배열을 선언한 뒤, 재귀함수로 큰 삼각형부터 그려준다.
공백은 ' '으로 표시해야하며, 더이상 *가 없다면 다음 라인으로 넘어가야
오답을 피할 수 있다.

#include <algorithm>
#include <cstdio>
using namespace std;
bool map[2500][2500];
int N,eg[11];
void prt(int n,int sy,int sx){ 
    if(n==0) return;
    int h=eg[n],w=(h-1)*2+1,d=1,ey,ex=sx+w-1;
    if(n%2==0) {
        ey=sy+h-1;
    }else{
        d=-1;
        ey=sy-h+1;
    }
    for(int i=sx;i<=ex;i++) map[sy][i] = 1;
    int k=1;
    for(int y=sy+d;y!=ey+d;y+=d,k++){
        map[y][sx+k] = map[y][ex-k] = 1;
    }
    prt(n-1,(sy+ey)/2,sx+h/2+1);
}
int main(){
    scanf("%d",&N);
    eg[1]=1;
    for(int i=2;i<=N;i++) eg[i]=eg[i-1]*2+1;
    int k=0,d=1;
    if(N%2) prt(N,eg[N]-1,0);
    else {
        k=eg[N]-1,d=-1;
        prt(N,0,0);
    }

    for(int i=0;i<eg[N];i++){
        for(int j=0;j<eg[N]+k;j++) printf("%c",map[i][j] ? '*':' ');  
        k+=d;
        if(i<eg[N]-1) puts("");
    }
}

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

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

[난이도] Gold4
[유형] DP

[풀이]
값이 1씩 증가하는 LIS를 구한다. 이 LIS에 포함되지 않은 숫자들은
모두 앞 또는 뒤로 옮겨줘야 정렬을 할 수 있기 때문에 N-(LIS의 길이) 가 정답이다.

#include <algorithm>
#include <cstdio>
using namespace std;
int N,dp[1000001],v,ans;
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
        scanf("%d",&v);
        dp[v] = dp[v-1]+1;
        ans = max(ans,dp[v]);
    }
    printf("%d",N-ans);
}

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

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

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

[풀이]
플로이드 와샬의 경로까지 출력해야 하는 문제이다.
최단경로를 갱신할 때 경유지 i,j의 경유지 k를 path[i][j]에 저장해놓고
이것을 이용해 재귀함수로 경로를 출력한다.

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
int N,M,dist[101][101],path[101][101],INF=9e8;
void prt(int i,int j,vector<int>& tmp){
    if(i==j) {
        tmp.push_back(i);
        return;
    }
    int p = path[i][j];
    prt(i,p,tmp);
    if(i!=p) prt(p,j,tmp);
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) if(i!=j) dist[i][j]=INF;  
             
    while(M--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(dist[a][b] > c){
           dist[a][b] = c;
           path[a][b] = 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];
                   path[i][j]=k;
                }
            }
        }
    }
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++)
            printf("%d ",dist[i][j]==INF ? 0 : dist[i][j]);
        puts("");
    }
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(!dist[i][j]) printf("0");
            else {
                vector<int> tmp;
                prt(i,j,tmp);
                tmp.push_back(j);
                printf("%d ",tmp.size());
                for(auto k : tmp) printf("%d ",k);
            }
            puts("");
        }
    }
}

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

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

[난이도] Gold4
[유형] DP

[풀이]

DP[n][m] : 현재 n 도시에 있고 m개의 도시를 지났을 때 얻을 수 있는 최대 점수

점화식
DP[n][m] max(adj[n][i]+sol(i,m+1)) : i는 n < i 이면서 n에서 i로 가는 경로 존재,
아무 도시도 갈 수 있다면 절대 나올 수 없는 값 -inf를 return하여 정답에서 제외.

#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
int N,M,K,adj[301][301],dp[301][301];
int sol(int n,int m){
    if(n==N) return 0;
    if(m==M) return -9e8;
    int& ret = dp[n][m];
    if(ret!=-1) return ret;
    ret = -9e8;
    for(int i=1;i<=N;i++) if(adj[n][i]) ret = max(ret,adj[n][i]+sol(i,m+1)); 
    return ret;
}
int main(){
    scanf("%d%d%d",&N,&M,&K);
    while(K--){
        int u,v,c;
        scanf("%d%d%d",&u,&v,&c);
        if(u<v) adj[u][v] = max(adj[u][v],c);
    }
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(1,1) > 0 ? sol(1,1):0);
}

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

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

[난이도] Gold4
[유형] DP

[풀이]
DP[l][r] : l~r의 DNA 서열의 부분 서열들 중에서 길이가 최대가 되는 KOI 유전자의 길이.

k를 l~r-1 증가시키면서 구한 max(DP[l][k]+dp[k+1][r]) 에다

만약 s[i],s[j]가 KOI 유전자일 때, 2+DP[i+1][j-1] 까지 비교해주면 DP[l][r]을 구할 수 있다.

#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
int dp[501][501];
char s[501];
int sol(int l,int r){
    if(l>=r) return 0;
    int& ret = dp[l][r];
    if(ret!=-1) return ret;
    ret = 0;
    if((s[l]=='g'&&s[r]=='c')||(s[l]=='a'&&s[r]=='t')) ret = 2+sol(l+1,r-1);
    for(int i=l;i<r;i++) ret = max(ret,sol(l,i)+sol(i+1,r));
    return ret;
}
int main(){
    scanf("%s",s);
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0,strlen(s)-1));
}

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

[BOJ/백준][Gold4] 2109 : 순회강연 (C++)

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

[난이도] Gold4
[유형] Greedy

[풀이]
i일에는 d가 i 이상인 강연만 할 수 있다.
앞에서부터 생각하면 복잡하므로 뒤에서부터 가능한 강연료를 우선순위 큐에 추가하면 된다.
10000일이 최대이므로 i를 10000 ~ 1로 순회하면서 d가 i인 강연의 강연료 p를 우선순위 큐에 push하고
1개를 뽑으면 i일에 할 수 있는 최적의 강연을 뽑을 수 있다.

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int N,ans;
vector<int> a[10001];
int main(){ 
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        int p,d;
        scanf("%d%d",&p,&d);
        a[d].push_back(p);
    }
    priority_queue<int> pq;
    for(int i=10000;i>0;i--){
        for(auto k : a[i]) pq.push(k);
        if(!pq.empty()){
            ans+=pq.top();
            pq.pop();
        }
    }
    printf("%d",ans);
}

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