프로그래밍

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

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

[난이도] Gold4
[유형] DP,Bitmask,완전탐색

[풀이]
next_permutation으로 푸니까 TLE로 틀려서 Bitmask DP로 풀었다.
선수 11명, 포지션 11개밖에 안되므로 DP[11][1<11] 배열로
11x2^11 O(22528) 안에 해결이 가능하다.

next_permutation이 아닌 재귀를 활용한 완전탐색으로도 0인 경우에 가지치기를 해주면
시간내에 해결이 가능하다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int tc,a[11][11],dp[11][1<<11],inf=-9e8;
int sol(int n,int msk){
    if(n==11) return 0;
    int& ret = dp[n][msk];
    if(ret!=-1) return ret;
    ret = inf;
    for(int i=0;i<11;i++){
        if(((1<<i)&msk)==0 && a[i][n]){
            ret = max(ret,sol(n+1,msk|(1<<i))+a[i][n]);
        }
    }
    return ret;
}
int main(){ 
    scanf("%d",&tc);
    while(tc--){
        for(int i=0;i<11;i++)
            for(int j=0;j<11;j++) scanf("%d",&a[i][j]);       
        memset(dp,-1,sizeof(dp));
        printf("%d\n",sol(0,0));
    }
}

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

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

[난이도] Gold4
[유형] BFS

[풀이]
BFS를 이용해 풀 수 있다.
각 문,거울에 번호를 준 뒤, 문,거울간에 인접행렬을 만들어서 풀수도 있지만
본인은 맵에서 한칸씩 움직이는 방식으로 풀었다.
메모제이션 배열은 visit[50][50][2]과 같이 선언해야 한다.
visit[y][x][0] -> 세로 방향에서 y,x에 도착한 경우.
visit[y][x][1] -> 가롱 방향에서 y,x에 도착한 경우.

두 방향으로 구분한 이유는 y,x에 거울을 설치할 수 있을 때,
세로 방향에서 왔을 때 거울을 설치하면 다음 방향으로 가로방향(좌,우)로 이동이 가능하고
가로 방향에서 왔으면 세로방향으로의 이동이 가능해지기 때문이다.
만약 visit[50][50]으로만 해놓고 풀면 방향전환을 할 수 없는 경우가 생기게 된다.

큐에는 {y,x,d,k}를 넣어준다. d는 현재 움직이고 있는 방향이고, k는 현재까지 사용한 거울 개수이다.
만약 '.'인 칸이면 그냥 d방향으로만 전진하고 거울설치가 가능한 '!' 칸이면 좌우로 방향이 바뀌는 경우도
k+1을 해주고 추가로 큐에 넣어주면 된다.

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int dy[4]={1,0,-1,0};
int dx[4]={0,1,0,-1};
int N,visit[50][50][2],sy=-1,sx,ey,ex;
char map[50][50];
struct P{
    int y,x,d,k;
};
int main(){ 
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            scanf(" %c",&map[i][j]);
            if(map[i][j]=='#') {
                if(sy==-1)sy=i,sx=j;
                else ey=i,ex=j;
            }
        }
    }
    memset(visit,-1,sizeof(visit));
    queue<P> q;
    for(int i=0;i<4;i++) {
        q.push({sy,sx,i,0});
        visit[sy][sx][i%2]=0;
    }
    while(!q.empty()){

        P f = q.front(); q.pop();
        int ny = f.y+dy[f.d], nx = f.x+dx[f.d];
        if(ny < 0 || nx < 0 || ny >= N || nx >= N || map[ny][nx]=='*') continue;
        
        if(visit[ny][nx][f.d%2]==-1 || visit[ny][nx][f.d%2] > f.k) {
            visit[ny][nx][f.d%2] = f.k;
            q.push({ny,nx,f.d,f.k});
        }        
        if(map[ny][nx]=='!'){
            if(visit[ny][nx][(f.d+1)%2]==-1 || visit[ny][nx][(f.d+1)%2] > f.k+1) {
                visit[ny][nx][(f.d+1)%2] = f.k+1;
                q.push({ny,nx,(f.d+1)%2,f.k+1});
                q.push({ny,nx,2+(f.d+1)%2,f.k+1});
            }            
        }
    }
    int ans = 9e8;
    if(visit[ey][ex][1]!=-1) ans = min(ans,visit[ey][ex][1]);
    if(visit[ey][ex][0]!=-1) ans = min(ans,visit[ey][ex][0]);
    printf("%d",ans);
}

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