프로그래밍

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

[난이도] Gold2
[유형] DP

[풀이]
높이순으로 정렬해놓고 어떤 그림들을 빼야 효율적인지를 정해야 한다.
일일히 구해보면 시간초과가 나므로 메모제이션을 이용해야 한다.
DP[i] : i~N-1번째 그림들에서 얻을 수 있는 최댓 값.

i번 그림은 포함될수도 있고, 제거(제일 뒤로 보내기)할 수도 있다.
1) 포함되는 경우.
만약 i번 그림이 포함된다면 p=(i번 그림의 높이 + S)보다 낮은 그림들은 가려져서 포함될 수 없다.
그러므로 p보다 높이가 높은 가장 작은 index를 k라고 했을 때,
(i번 그림의 가격 + DP[k])이 첫번째 케이스의 결과이다.

2) 포함되지 않는 경우.
i번 그림이 아무것도 가리지 않게 되므로 DP[i]==DP[i+1]이므로
DP[i+1]이 두번째 케이스의 결과이다.

=> DP[i] = 1,2케이스 중에 더 큰 값.

Top-Down 방식으로 구현하였다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N,S,dp[300000],h[300000];
pair<int,int> a[300000];
int sol(int n){
    if(n>=N) return 0;
    int& ret=dp[n];
    if(ret!=-1) return ret;

    int p = a[n].first+S;
    int k = lower_bound(h,h+N,p)-h;
    ret=sol(n+1);
    ret=max(ret,a[n].second+sol(k));

    return ret;
}
int main(){
    scanf("%d%d",&N,&S);
    for(int i=0;i<N;i++) {
        scanf("%d%d",&a[i].first,&a[i].second);
        h[i]=a[i].first;
    }
    sort(h,h+N);
    sort(a,a+N);
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0));
}

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

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

[난이도] Gold2
[유형] BFS

[풀이]
모든 경우에 6가지 물통간 이동이 가능하다. 6^k 개씩 계속 경우가 늘어날 것 같지만
(p,q)를 현재 A,B 물통의 물의 양이라고 했을 때, (p,q)의 경우의 수가 몇개 나오지 않는다고 한다.
(정확한 증명은 어렵지만 물을 전체 다넣거나, 전체 다빼거나, 전체 다옮기거나 하는 단순한 연산들만 반복해서 그렇게 되는 것 같다.)

BFS인 것을 눈치채도 A,B가 최대 100000까지 나오므로 배열로는 메모리 초과를 당하게 된다.

그러므로 set memo[100001]; 와 같이 set을 이용해야 한다.
(1,3)이라면 mem[1].insert(3) 과 같이 저장할 수 있다.
이후 풀이는 일반 BFS와 동일하다.

#include <cstdio>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
int cap[2],tar[2];
set<int> memo[100001];
queue<pair<int,int>> q;
int main(){
    scanf("%d%d%d%d",&cap[0],&cap[1],&tar[0],&tar[1]);

    q.push({0,0});
    memo[0].insert(0);
    int ret=0;
    while(!q.empty()){

        int sz=q.size();
        while(sz--){
            auto qf = q.front(); q.pop();
            int v[2];
            v[0]=qf.first, v[1]=qf.second;
            if(v[0]==tar[0] && v[1]==tar[1]){
                printf("%d",ret);
                return 0;
            }
            for(int i=0;i<6;i++){
                int a,b;
                if(i==0) a=cap[0],b=v[1];
                else if(i==1) a=v[0],b=cap[1];
                else if(i==2) a=0,b=v[1];
                else if(i==3) a=v[0],b=0;
                else if(i==4) a=min(cap[0],v[0]+v[1]), b=v[1]-min(cap[0]-v[0],v[1]);
                else a=v[0]-min(cap[1]-v[1],v[0]),b=min(cap[1],v[1]+v[0]);

                if(memo[a].find(b) == memo[a].end()){
                    memo[a].insert(b);
                    q.push({a,b});
                }
            }
        }
        ret++;
    }
    puts("-1");
}

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

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

[난이도] Gold2
[유형] DFS

[풀이]
N,M의 최댓값이 1000이므로 각 점에서 DFS or BFS로 답을 구하면 시간 초과가 난다.
DFS를 전체 맵에 대해 한번씩 돌리면서 빈 칸이 어떤 그룹에 속하는지, 그 그룹의 총 원소의 수는 몇개인지를 기록해놓는다.
그 뒤 맵을 다시 순회하면서 벽이 있는 칸의 4방향을 확인하면서 그룹의 갯수를 더해주면 시간내에 답을 구할 수 있다.

#include <cstdio>
#include <set>
using namespace std;
int dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
int N,M,a[1000][1000],grp[1000][1000],cnt[1000001];
bool visit[1000][1000];
int dfs(int y,int x,int k){
    visit[y][x]=1;
    grp[y][x]=k;

    int ret=1;
    for(int i=0;i<4;i++){
        int ny=y+dy[i], nx=x+dx[i];
        if(ny<0||nx<0||ny>=N||nx>=M||a[ny][nx]||visit[ny][nx]) continue;
        ret+=dfs(ny,nx,k);
    }
    return ret;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) scanf("%1d",&a[i][j]);
        
    int g=1;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(!a[i][j] && !visit[i][j]){
                cnt[g]=dfs(i,j,g);
                g++;
            }
        }
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(!a[i][j]) continue;
            int v=0;
            set<int> p;
            for(int k=0;k<4;k++){
                int ny=i+dy[k],nx=j+dx[k];
                if(ny<0||nx<0||ny>=N||nx>=M||a[ny][nx]) continue;  
                p.insert(grp[ny][nx]);
            }
            for(auto q : p) v+=cnt[q];
            a[i][j]=v+1;
        }
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            printf("%d",a[i][j]%10);
        }
        puts("");
    }
}

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

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

[난이도] Gold3
[유형] DP

[풀이]
DP[y][x] : y,x에서 출발해서 목적지(ay,ax)로 갈 수 있는 경로의 수
ay,ax를 토스트집의 좌표로 설정한 뒤 DP[1][1]을 구한 값,
ay,ax를 h,w로 설정한 뒤 DP[토스트집의 Y][토스트집의 X]를 구한 값을 곱하면 된다.

1000007로 계산시 나눠줘야 하며 위의 두 값을 곱할 때 int 범위를 넘어갈 수 있으므로
long long으로 계산해야 한다.

#include <cstdio>
#include <cstring>
using namespace std;
int w,h,mod=1000007,ax,ay,dp[201][201];

int sol(int y,int x){
    if(y==ay&&x==ax) return 1;

    int& ret = dp[y][x];
    if(ret!=-1) return ret;
    ret=0;
    if(y+1<=h) ret = sol(y+1,x);
    if(x+1<=w) ret += sol(y,x+1);
    return ret%=mod;
}
int main(){
    scanf("%d%d%d%d",&w,&h,&ax,&ay);

    memset(dp,-1,sizeof(dp));
    long long ans=sol(1,1);

    int sy=ay,sx=ax;
    ay=h,ax=w;

    memset(dp,-1,sizeof(dp));
    ans*=sol(sy,sx);
    
    printf("%lld",ans%mod);
}

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

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

[난이도] Gold3
[유형] DP

[풀이]
DP

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
int N,dp[400][400][400],v,inf=-8e7,as,bs;
vector<int> arr[2];
int sol(int n,int a,int b){
    if(a==as||b==bs) return 0;
    int& ret = dp[n][a][b];
    if(ret!=inf) return ret;
    ret=sol(n+1,a+1,b+1)+arr[0][a]*arr[1][b];
    if(N>n+as-a) ret=max(ret,sol(n+1,a,b+1));
    if(N>n+bs-b) ret=max(ret,sol(n+1,a+1,b));
    return ret;
}
int main(){
    scanf("%d",&N);
    for(int j=0;j<2;j++){
        for(int i=0;i<N;i++){
            scanf("%d",&v);
            if(v!=0) arr[j].push_back(v);
        }
    }
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            for(int k=0;k<N;k++) dp[i][j][k]=inf;
    as=arr[0].size(),bs=arr[1].size();
    printf("%d",sol(0,0,0));
}

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

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

[난이도] Gold3
[유형] DFS

[풀이]
정방향,반대방향 인접 리스트를 이용해서 dfs를 두번하면 최대,최저 등수를 구할 수 있다.

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
vector<int> adj[2][100001];
bool visit[100001];
int N,M,X,k;
int dfs(int n){
    visit[n]=1;
    int ret=1;
    for(auto v : adj[k][n]){
        if(!visit[v]) ret+=dfs(v);
    }
    return ret;
}
int main(){
    scanf("%d%d%d",&N,&M,&X);
    for(int i=0;i<M;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        adj[0][u].push_back(v);
        adj[1][v].push_back(u);
    }
    int U,V;
    U=N-dfs(X)+1;
    k=1;
    V=dfs(X);
    printf("%d %d",V,U);
}

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

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

[난이도] Gold3
[유형] 스위핑

[풀이]
idea : 1) 어차피 M까지 가야하므로 정방향으로 가는 사람들은 고려할 필요가 없다.
2) 반대로 가는 사람들 때문에 돌아가야하는 추가 이동거리가 발생하는데,
5->2, 6->3 이렇게 겹치는 경로가 있는 사람들끼리 묶어서 뒤로 이동하는것이 가장 효율적이다.
3) a>b인 (a,b) 입력에 대해 (b,a) pair로 vector에 저장 뒤 정렬 후,
스위핑을 해주면서 묶인 집합의 길이*2를 답에 더해주면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
int N;
ll M;
vector<pair<ll,ll>> v;
int main(){
    scanf("%d%lld",&N,&M);
    for(int i=0;i<N;i++) {
        ll u,r;
        scanf("%lld%lld",&u,&r);
        if(u>r) v.push_back({r,u});
    }
    sort(v.begin(),v.end());

    ll s=v[0].first, e=v[0].second;
    for(auto p : v){
        if(e<p.first){
            M+=2*(e-s);
            s=p.first,e=p.second;
        }else if(e<p.second){
            e=p.second;
        }
    }
    M+=2*(e-s);
    printf("%lld",M);
}

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

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

[난이도] Gold5
[유형] 스위핑

[풀이]
1. pair 배열 에 (시작점,끝점)으로 저장 뒤 시작점을 기준으로 오름차순 정렬한다.
2. s:현재 긋고 있는 선의 시작점, e:현재 긋고 있는 선의 끝점
3. 앞에서부터 pair 의 선들을 확인하면서 선이 s~e에 포함되면 skip, 선의 앞이 e보다 작거나 같고 뒤가 e보다 큰 경우
e를 업데이트, 선의 앞이 e보다 크면 e-s를 답에 저장하고 s,e를 새로 업데이트.

위 방식으로 누적된 길이가 그리는 선의 최종 길이이다.

#include <cstdio>
#include <algorithm>
using namespace std;
int N;
pair<int,int> a[1000000];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d%d",&a[i].first,&a[i].second);
    
    sort(a,a+N); 
    int s=a[0].first,e=a[0].second;
    int d=0;
    for(int i=1;i<N;i++){
        if(a[i].first<=e) {
            if(e<a[i].second) e=a[i].second;
        }
        else {
            d+=e-s;
            s=a[i].first;
            e=a[i].second;
        } 
    }
    d+=e-s;
    printf("%d",d);
}

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