프로그래밍

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

[난이도] Gold4
[유형] DP

[풀이]
DP[n][m] : 첫번째 문자열의 문자를 앞에서부터 n개 사용했고, 두번째 문자열의 문자를 앞에서부터 m개 사용했을 때,
           세번째 문자열의 아직 사용하지 않은 문자열을 채울 수 있으면 1, 없으면 0을 return

#include <string>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int tc,dp[201][201];
string a,b,c;
int sol(int n,int m){
    if(n+m==c.size()) return 1;
    int& ret = dp[n][m];
    if(ret!=-1) return ret;
    if(n<a.size() && c[n+m]==a[n] && sol(n+1,m)) return ret=1;
    if(m<b.size() && c[n+m]==b[m] && sol(n,m+1)) return ret=1;
    return ret=0;
}
int main(){
    scanf("%d",&tc);
    for(int i=1;i<=tc;i++){
        cin >> a >> b >> c;
        memset(dp,-1,sizeof(dp));
        string ret = sol(0,0) ? "yes":"no";
        cout << "Data set " << i << ": " << ret << '\n';
    }
}

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

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

[난이도] Gold4
[유형] DP

[풀이]
어떤 칸 (r,c) 의 한 숫자를 선택할 경우 어차피 r-1,r+1행은 선택할 수가 없습니다.
그러므로 r행의 숫자들을 선택할 때 이왕이면 최대한 많은 사탕을 선택하는 것이 좋습니다.

r행에서 선택할 수 있는 사탕의 최댓값은 dp를 이용해 구할 수 있습니다.
그리고 구한 값을 maxv 배열에 저장해 놓은 뒤

이 배열의 값을 이용해 같은 방식으로 어떤 열이 선택되는지를 dp로 구해주면 됩니다.
dp2[r] : r행을 선택 했을 때, 얻을 수 있는 사탕의 최대 개수.
dp2[r] = maxv[r]+max(dp2[r+2],dp2[r+3]);

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstring>
using namespace std;
int M,N,board[200000],dp1[200000],dp2[200000],maxv[200000];
int sol(int r,int c){
    if(c>=N) return 0;
    int& ret = dp1[r*N+c];
    if(ret!=-1) return ret;
    return ret=board[r*N+c]+max(sol(r,c+2),sol(r,c+3));
}
int sol2(int r){
    if(r>=M) return 0;
    int& ret =dp2[r];
    if(ret!=-1) return ret;
    return ret=maxv[r]+max(sol2(r+2),sol2(r+3));
}
int main(){
    while(1){
        scanf("%d%d",&M,&N);
        if(N==0 && M==0) break;
        memset(dp1,-1,sizeof(dp1));
        memset(dp2,-1,sizeof(dp2));
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
                int v;
                scanf("%d",&v);
                board[i*N+j]=v;
            }
            maxv[i] = max(sol(i,0),sol(i,1));
        }
        printf("%d\n",max(sol2(0),sol2(1)));
    }
}

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

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

[난이도] Gold4
[유형] DP

[풀이]
dp[a][b] : 전체 돌의 개수가 T이면서 a<=b<=T-a-b 일 때, 세 개의 돌을 같게 만들 수 있으면 1,
           아니면 0을 저장

위와 같이 점화식을 세운 뒤, a<=b<=T-a-b 조건을 만족하도록 정렬해주면서
Top-Down dp 함수를 짜주면 됩니다.
이전 상태로 돌아가지 않도록 visit 배열을 선언하면 방문 여부를 체크해주었습니다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int arr[3],dp[501][501],T,visit[501][501];
int sol(int a,int b){
    if(a<=0 || b<=0 || T-a-b<=0) return 0;
    if(a==b && a==T-a-b) return 1;
    if(visit[a][b]) return 0;
    visit[a][b]=1;
    int& ret = dp[a][b];
    if(ret!=-1) return ret;

    int tmp[3];
    int A=a,B=b,C=T-A-B;

    tmp[0]=2*A,tmp[1]=B-A,tmp[2]=C;
    sort(tmp,tmp+3);
    if(sol(tmp[0],tmp[1])) return ret=1;

    tmp[0]=A,tmp[1]=2*B,tmp[2]=C-B;
    sort(tmp,tmp+3);
    if(sol(tmp[0],tmp[1])) return ret=1;

    tmp[0]=2*A,tmp[1]=B,tmp[2]=C-A;
    sort(tmp,tmp+3);
    if(sol(tmp[0],tmp[1])) return ret=1;

    return ret=0;
}

int main(){
    for(int i=0;i<3;i++) {
        scanf("%d",&arr[i]);
        T+=arr[i];
    }
    sort(arr,arr+3);
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(arr[0],arr[1]));
}

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

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

[난이도] Gold4
[유형] Greedy

[풀이]
거리의 합이 최소가 될때 유리하게 만들기 위해서는

우체국의 위치를 x라고 했을 때, x에 마을이 많을수록,
x를 기준으로 좌우에 퍼져있는 우체국의 수가 비슷할수록 유리합니다.

결국 마을위 위치를 기준으로 정렬한 뒤,
1~N 마을을 순회하면서 사람 수를 cur에 더해나갑니다.
그러다 cur>=(sum(전체 사람 수)+1)/2 를 만족하는 순간의 i가 우체국이 설치되었을 때
가장 유리한 마을의 index입니다.

#include <cstdio>
#include <algorithm>
using namespace std;
using ll = long long;
int N;
pair<ll,ll> xa[100001];

int main(){
    scanf("%d",&N);
    ll sum=0;
    for(int i=1;i<=N;i++) {
        scanf("%lld%lld",&xa[i].first,&xa[i].second);
        sum+=xa[i].second;
    }
    sort(xa+1,xa+N+1);

    ll cur=0;
    for(int i=1;i<=N;i++){
        cur+=xa[i].second;
        if(cur>=(sum+1)/2) {
            printf("%d",xa[i].first);
            break;
        }
    }
}

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

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

[난이도] Gold4
[유형] BFS

[풀이]
왼쪽 끝점을 기준으로 BFS를 돌려줍니다.
직사각형을 옮길 수 있을지 판단할 때, 세로H, 가로W의 모든 점을 검사하면 시간초과가 발생하게 되므로
누적합 배열을 미리 만들어 놓은 뒤, 옮길 위치의 사각형에 1(벽)이 포함되어 있는지를 O(1)에 판별하도록 해줍니다.

#include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;
int N,M,board[1001][1001],H,W,sy,sx,ey,ex,sum[1001][1001];
bool visit[1001][1001];
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,1,-1};
bool check(int y,int x){
    if(y<1||x<1||y>N||x>M||y+H-1<1||x+W-1<1||y+H-1>N||x+W-1>M) return 0;
    if(sum[y+H-1][x+W-1]-sum[y-1][x+W-1]-sum[y+H-1][x-1]+sum[y-1][x-1]>0) return 0;
    return 1;
}
int bfs(){
    queue<pair<int,int>> q;
    q.push({sy,sx});
    visit[sy][sx]=1;
    int ret=0;
    while(!q.empty()){
        int sz= q.size();
        while(sz--){
            auto [y,x] =q.front(); q.pop();
            if(y==ey&&x==ex) return ret;
            for(int i=0;i<4;i++){
                int ny=y+dy[i];
                int nx=x+dx[i];
                if(!check(ny,nx) || visit[ny][nx]) continue;
                q.push({ny,nx});
                visit[ny][nx]=1;
            }
        }
        ret++;
    }
    return -1;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++) {
            scanf("%d",&board[i][j]);
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+board[i][j];
        }

    scanf("%d%d%d%d%d%d",&H,&W,&sy,&sx,&ey,&ex);
    printf("%d",bfs());
}

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

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

[난이도] Gold4
[유형] 우선순위큐

[풀이]
https://www.acmicpc.net/problem/11066 문제와 다른점은
꼭 연속된 파일을 합칠 필요가 없이 아무 파일이나 두개를 골라서 합쳐도 된다는 것입니다.

우선순위큐에 모든 파일의 크기를 넣어놓고 작은 것부터 꺼내서 합친 뒤, 다시 넣고를 반복하다
최종적으로 남게되는 1개의 파일의 크기가 최종 정답입니다.

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
using ll = long long;
int T,K;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&K);
        priority_queue<ll,vector<ll>,greater<ll>> pq;
        for(int i=0;i<K;i++) {
            int v;
            scanf("%d",&v);
            pq.push(v);
        }
        ll ans=0;
        while(pq.size()>1){
            ll a = pq.top(); pq.pop();
            ll b = pq.top(); pq.pop();
            pq.push(a+b);
            ans+=a+b;
        }
        printf("%lld\n",ans);
    }
}

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

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

[난이도] Gold4
[유형] BFS

[풀이]
K마리의 소로 만들 수 있는 모든 쌍에 대해
길을 건너지 않고 서로 방문할 수 있는 쌍의 개수를 찾으면 됩니다.
길을 저장할 때 adj[101][101][101][101] 형식의 배열로 저장하는 것은 배열의 메모리 문제로
불가능 하므로 (r1,c1)<->(r2,c2) 의 길은 set<int> adj[20001] 형태의 set을 선언하여
adj[r1*N+c1].insert(r2*N+c2) 와 같이 set을 이용하여 저장해줍니다.

그 뒤, 모든 쌍의 소 간에 BFS를 통해 위에 미리 저장해놓은 길을 이용하지 않고 방문할 수 있는지를
구해주어, 정답에 방문할 수 있으면 0, 방문할 수 없으면 1을 더해주면
길을 건너지 않으면 만날 수 없는 소의 쌍을 구할 수 있습니다.

#include <cstdio>
#include <queue>
#include <set>
#include <vector>
#include <cstring>
using namespace std;
int N,K,R;
bool visit[101][101];
int dy[4]={-1,1,0,0};
int dx[4]={0,0,1,-1};
set<int> adj[20001];
vector<pair<int,int>> v;
int sol(int s,int e){
    memset(visit,0,sizeof(visit));
    queue<pair<int,int>> q;
    q.push({v[s].first,v[s].second});
    visit[v[s].first][v[s].second]=1;
    while(!q.empty()){
        auto [y,x] = q.front(); q.pop();
        if(y==v[e].first && x==v[e].second) return 0;
        for(int i=0;i<4;i++){
            int ny=y+dy[i],nx=x+dx[i];
            if(ny<1||nx<1||ny>N||nx>N||visit[ny][nx]||adj[y*N+x].find(ny*N+nx) != adj[y*N+x].end()) continue;
            q.push({ny,nx});
            visit[ny][nx]=1;
        }
    }
    return 1;
}
int main(){
    scanf("%d%d%d",&N,&K,&R);
    while(R--){
        int r1,c1,r2,c2;
        scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
        adj[r1*N+c1].insert(r2*N+c2);
        adj[r2*N+c2].insert(r1*N+c1);
    }
    while(K--){
        int y,x;
        scanf("%d%d",&y,&x);
        v.push_back({y,x});
    }
    int ans=0;
    for(int i=0;i<v.size()-1;i++)
        for(int j=i+1;j<v.size();j++) ans+=sol(i,j);
    printf("%d",ans);
}

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

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

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

[풀이]
2N 크기의 벨트 배열과, N 크기의 로봇 배열을 선언하여,
매 단계마다 조건에 맞게 업데이트 해주면 되는 문제입니다.
구현이 까다롭기 보다는 문제의 지문을 정확히 해석하는 능력이 더 중요한 문제입니다.

#include <cstdio>
using namespace std;
int N,K,robot[101],belt[201];
int main(){
    scanf("%d%d",&N,&K);
    for(int i=1;i<=2*N;i++) scanf("%d",&belt[i]);
    int ret=1;
    while(1){
        for(int i=N;i>=2;i--) robot[i]=robot[i-1];
        robot[1]=robot[N]=0;
        int t = belt[2*N];
        for(int i=2*N;i>=2;i--) belt[i]=belt[i-1];
        belt[1]=t;

        for(int i=N-1;i>=2;i--) {
            if(robot[i] && !robot[i+1] && belt[i+1]>=1) {
                belt[i+1]--;
                robot[i]=0;
                if(i+1!=N) robot[i+1]=1;
            }
        } 
        if(belt[1]>0) {
            robot[1]=1;
            belt[1]--;
        }
        int cnt=0;
        for(int i=1;i<=2*N;i++) if(belt[i]==0) cnt++;

        if(cnt>=K) break;
        ret++;
    }
    printf("%d",ret);
}

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