프로그래밍

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

[난이도] Gold5
[유형] DP

[풀이]
DP[n][m] : n번째 원소부터 선택이 가능하고 현재까지 총 m개의 구간을 구했을 때, 만들 수 있는 최댓값

부분합을 미리 구해놓는다 -> sum[i][j] : i~j까지의 합.

Top-Down 방식으로 풀었다. sol(n,m) 은 DP[n][m]

점화식 :
1) n번째 원소를 어느구간에도 포함시키지 않는 경우
=> sol(n,m) = sol(n+1,m) (구간은 증가하지 않고 n만 1 증가)

2) n번째 원소를 첫번째 원소로 해서 만들 수 있는 모든 구간을 구해보는 경우
=> sol(n,m) = max(sum[n][i]+sol(i+2,m+1)) ( n <= i < N )

1,2의 최댓값이 정답이다.

종료조건 :
m==M 인 경우 => 모든 구간을 다 찾았으므로 0을 return
m=N인 경우 => 새로운 구간을 만들 수 없으므로 음의 무한대 -9e8을 return

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N,M,a[100],dp[100][51],sum[100][100],inf=9e8;
int sol(int n,int m){
    if(m==M) return 0;
    if(n>=N) return -inf;
    int& ret = dp[n][m];
    if(ret!=-1) return ret;
    ret=sol(n+1,m);
    for(int i=n;i<N;i++){
        ret=max(ret,sum[n][i]+sol(i+2,m+1));
    }
    return ret;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<N;i++){
        int s = 0;
        for(int j=i;j<N;j++){
            s+=a[j];
            sum[i][j]=s;
        }
    }
    printf("%d",sol(0,0));
}

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

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

[난이도] Gold5
[유형] 브루트포스

[풀이]
N제한이 20이므로 재귀를 이용한 브루트포스로 해결이 가능하다.

sol(n,cnt) 는 n번째 벽장을 사용할 차례일 때, 현재까지 cnt번 움직인 상태이다.

a[20] 배열에는 현재 열려있는 벽장은 1, 닫혀있는 벽장은 0으로 상태가 저장되어있다.
seq[i]는 i번째로 움직일 벽장의 번호이다.
sol(n,cnt)에서

a[seq[n]]이 1이라면 이미 열려있으므로 cnt 증가 없이 sol(n+1,cnt)으로 넘어가면 되고,

아니라면 벽장을 좌측 또는 우측으로 밀어야 하므로 열려있는 벽장의 인덱스를 idx에 저장한 뒤
우측 : sol(n+1,idx-cur+cnt)
좌측 : sol(n+1,cur-idx+cnt)

위와 같이 재귀함수를 진행해 나가면 답을 찾을 수 있다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N,M,a[20],seq[20],ans=9e8;
void sol(int n,int cnt){
    if(n==M){
        ans=min(ans,cnt);
        return;
    }
    int cur = seq[n];
    if(a[cur]){
        sol(n+1,cnt);
    }else{  
        int idx=-1;
        for(int i=cur;i<N;i++){
            if(a[i]){
                idx=i;
                break;
            }
        }
        if(idx!=-1){
            a[cur]=1;
            a[idx]=0;
            sol(n+1,idx-cur+cnt);
            a[cur]=0;
            a[idx]=1;
        }
        idx=-1;

        for(int i=cur;i>=0;i--){
            if(a[i]){
                idx=i;
                break;
            }
        }     
        if(idx!=-1){
            a[cur]=1;
            a[idx]=0;
            sol(n+1,cur-idx+cnt);
            a[cur]=0;
            a[idx]=1;
        }
    }
}
int main(){
    int t1,t2;
    scanf("%d%d%d%d",&N,&t1,&t2,&M);
    a[t1-1]=a[t2-1]=1;
    for(int i=0;i<M;i++){
        int v;
        scanf("%d",&v);
        seq[i]=v-1;
    }
    sol(0,0);
    printf("%d",ans);
}

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

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

[난이도] Gold5
[유형] BFS

[풀이]
바이러스가 위치할 수 있는 좌표의 최대 개수가 10개이므로 최초 바이러스의 개수 M개가
위치할 수 있는 모든 경우에 대해 BFS를 통해 시간을 구해주면 된다.
K개중에 M개를 선택하는 경우를 구하는 방법은 재귀로 해도 되지만
next_permutation을 이용해서 구할 수도 있다.
K가 5, M이 3일 때,
크기 5짜리 vector에 {0,0,1,1,1}와 같이 원소를 삽입하고,
next_permutation을 돌려주면 5개의 위치에서 세개를 고르는 모든 경우가 나온다.

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N,M,map[52][52],total,Inf=9e8;
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,1,-1};
bool visit[52][52];
vector<pair<int,int>> a;
vector<int> use;
int bfs(){
    memset(visit,0,sizeof(visit));
    queue<pair<int,int>> q;
    int ret=0,sum=0;    
    for(int i=0;i<use.size();i++){
        if(use[i]){
            q.push({a[i].first,a[i].second});
            visit[a[i].first][a[i].second]=1;
            sum++;
        }
    }
    while(!q.empty()){
        int sz = q.size();
        while(sz--){
            auto qf = q.front(); q.pop();
            int y = qf.first;
            int x = qf.second;
            for(int i=0;i<4;i++){
                int ny = y+dy[i];
                int nx = x+dx[i];
                if(ny<0||nx<0||ny>=N||nx>=N||map[ny][nx]==1||visit[ny][nx]) continue;
                q.push({ny,nx});
                visit[ny][nx]=1;
                sum++;
            }
        }
        ret++;
    }
    return total==sum ? ret-1 : Inf;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++) {
            scanf("%d",&map[i][j]);
            if(map[i][j]==2) a.push_back({i,j});
            if(map[i][j]!=1) total++;
        }
    use.resize((int)a.size());
    for(int i=0;i<M;i++) use[i]=1;
    reverse(use.begin(),use.end());
    int ans = Inf;
    do{
        ans = min(ans,bfs());
    }while(next_permutation(use.begin(),use.end()));
    if(ans==Inf) ans=-1;
    printf("%d",ans);
}

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

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

[난이도] Gold5
[유형] DP

[풀이]
dp[i] : i원을 만들 수 있는 경우의 수.

#include <cstdio>
#include <cstring>
using namespace std;
int tc,N,M,a[20],dp[10001];
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&N);
        memset(dp,0,sizeof(dp));
        for(int i=0;i<N;i++) scanf("%d",&a[i]);
        scanf("%d",&M);
        dp[0]=1;
        for(int i=0;i<N;i++)
            for(int j=1;j<=M;j++)
                if(j-a[i]>=0) dp[j]+=dp[j-a[i]];
        printf("%d\n",dp[M]);
    }
}

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

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

[난이도] Gold5
[유형] 시뮬레이션

[풀이]
문제의 조건대로 정확하게 시뮬레이션 해준다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N,M,K,ans;
int dy[8] = {-1,-1,0,1,1,1,0,-1};
int dx[8] = {0,1,1,1,0,-1,-1,-1};
struct P{
    int m,s,d;
};
vector<P> map[51][51],tmp[51][51];
void clear(vector<P> a[][51]){
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) a[i][j].clear();
}
void move(int i,int j){
    for(auto p : map[i][j]){
        int ny=i,nx=j;
        for(int k=0;k<p.s;k++){
            ny+=dy[p.d];
            nx+=dx[p.d];
            if(ny>N) ny=1;
            else if(ny<1) ny=N;
            if(nx>N) nx=1;
            else if(nx<1) nx=N;            
        }
        tmp[ny][nx].push_back(p);
    }   
}
void merge(int y,int x){
    if(tmp[y][x].size()<2) {
        map[y][x]=tmp[y][x];
        return;
    }
    int sm=0,ss=0,sd=0;

    for(auto p : tmp[y][x]){
        sm+=p.m;
        ss+=p.s;
        sd+=p.d%2;
    }
    int sz = tmp[y][x].size();
    int tm = sm/5;
    if(tm==0) return;
    int ts = ss/sz;
    int td;
    if(sd == sz || sd == 0) td = 0;
    else td = 1;
    for(;td<8;td+=2) map[y][x].push_back({tm,ts,td});
}
void cmd(){
    clear(tmp);
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            move(i,j);
        }
    }
    clear(map);
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            merge(i,j);
        }
    }    
}
int main(){
    scanf("%d%d%d",&N,&M,&K);
    while(M--){
        int r,c,m,s,d;
        scanf("%d%d%d%d%d",&r,&c,&m,&s,&d);
        map[r][c].push_back({m,s,d});
    }
    while(K--) cmd();
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++){
            for(auto p : map[i][j]) ans+=p.m;
        }
    printf("%d",ans);
}

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

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

[난이도] Gold5
[유형] 수학

[풀이]
N개의 소시지를 이어붙힌 뒤에 M등분을 해줘야 한다.

M-1번은 잘라야 하지만, 이어붙힌 소시지는 이미 N-1번 잘려있고 이 잘린 부분이
우리가 잘라야 하는 M-1번 자르는 부분과 겹칠 수 있으므로 이만큼은 M-1에서 빼줘야한다.
겹치는 부분은 (N과 M의 최대공약수)-1 이므로 정답은 M-1-(gcd(N,M)-1) = M-gcd(N,M) 이다.

#include <cstdio>
#include <algorithm>
using namespace std;
int N,M;
int gcd(int a,int b){
    if(a>b) swap(a,b);
    while(a>0){
        int c = b%a;
        b=a;
        a=c;
    }
    return b;
}
int main(){
    scanf("%d%d",&N,&M);
    printf("%d",M-gcd(N,M));
} 

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

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

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

[풀이]
0~W-1 열이 있을 때 어떤 인덱스 i 열에 고이는 물의 양을 구하려면
1) 1~i-1 블록의 높이중 최댓값, i+1~W-1 블록의 높이중 최댓값을 구하고
둘중 더 작은 값 k를 구한다.
2) i 블록의 높이 h가 k보다 작다면 물이 고일 수 있고 그 양은 k-h 만큼이다.

이런식으로 1~W-2 블록을 순회하면서 각 열에서 고일 수 있는 물을 더해주면 된다.

#include <cstdio>
#include <algorithm>
using namespace std;
int H,W,a[500];
int getMax(int l,int r){
    int ret=0;
    for(int i=l;i<=r;i++){
        ret=max(a[i],ret);
    }
    return ret;
}
int main(){
    scanf("%d%d",&H,&W);
    for(int i=0;i<W;i++) scanf("%d",&a[i]);
    int ans=0;
    for(int i=1;i<W-1;i++){
        int k = min(getMax(0,i-1),getMax(i+1,W-1));
        if(a[i]<k) ans+=k-a[i];
    }
    printf("%d",ans);
} 

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

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

[난이도] Gold5
[유형] union find

[풀이]
union find를 이용해서 서로 접근 가능한 점들을 한 그룹으로 묶어준다. N이 3000이므로 N^2으로 해결이 가능하다.

#include <cstdio>
#include <cstring>
using namespace std;
struct P{
    int x,y,r;
};
int T,N,uf[3000];
bool check[3000];
P a[3000];
int find(int n){
    if(uf[n]==n) return n;
    return find(uf[n]);
}
void merge(int n,int m){
    n=find(n);
    m=find(m);
    uf[n] = m;
}
int adj(int i,int j){
    int d = (a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y);
    return d <= (a[i].r+a[j].r)*(a[i].r+a[j].r);
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&N);
        for(int i=0;i<N;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].r);

        for(int i=0;i<N;i++) uf[i]=i;

        for(int i=0;i<N-1;i++){
            for(int j=i+1;j<N;j++){
                if(adj(i,j)) merge(i,j);
            }
        }

        memset(check,0,sizeof(check));
        int ans=0;
        for(int i=0;i<N;i++){
            int p = find(i);
            if(!check[p]){
                ans++;
                check[p]=1;
            }
        }
        printf("%d\n",ans);
    }
} 

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