프로그래밍

www.acmicpc.net/problem/2457  

[난이도] Gold4

[유형] Greedy

[풀이]

pair vector를 만들어서 first에 꽃이 피는날 second에 꽃이 지는날을 저장 후 정렬.

0~N-1 루프를 돌면서 최적의 꽃을 찾아주면 된다.

코드에서 s는 현재까지 꽃이 무조건 피어있다고 보장되는 날이다.

first가 s이하인 꽃들 중에서 second가 가장 큰 값을 mxr에 갱신해서 찾는다.

first가 s를 넘어가게 되면 위의 mxr이 최대인 꽃을 선택하고 다음 꽃을 찾는다.

이 때, 꽃이 피어있다고 보장되는나 s는 mxr로 갱신시킨다.

위의 과정을 반복하면 된다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int a[] = {0,31,28,31,30,31,30,31,31,30,31,30,31},base[13];
int N,ans;
vector<pair<int,int>> v;
int main(){
    for(int i=1;i<=12;i++) base[i]=a[i-1]+base[i-1];
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        int b[4];
        for(int j=0;j<4;j++) scanf("%d",&b[j]);
        v.push_back({base[b[0]]+b[1],base[b[2]]+b[3]});
    }
    sort(v.begin(),v.end());

    int s=base[3]+1,e=base[11]+30,mxr=-1,ok=0;
    for(int i=0;i<N;i++){
        auto p = v[i];
        int l=p.first,r=p.second;
        if(l<=s) {
            mxr=max(r,mxr);
            if(mxr > e){
                ok=1;
                ans++;
                break;
            }
        }
        else {
            if(mxr==-1) break;
            ans++;
            s=mxr;
            mxr=-1;
            i--;
        }
    }
    printf("%d",ok?ans:0);
}

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

www.acmicpc.net/problem/1695

[난이도] Gold4

[유형] DP

[풀이]

top-down dp로 해결할 수 있다.

sol(l,r) : 왼쪽 index가 l, 오른쪽이 r일때 팰린드롬을 만들기 위해 추가해야되는 숫자의 개수.

점화식

case l==r : sol(l,r) = sol(l+1,r-1)

case l!=r : sol(l,r) = min(sol(l,r-1)+sol(l+1,r))

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,a[5000],dp[5000][5000];

int sol(int l,int r){
    if(l>=r) return 0;
    int& ret = dp[l][r];
    if(ret !=-1) return ret;
    if(a[l]==a[r]) ret = sol(l+1,r-1);
    else ret = min(sol(l,r-1),sol(l+1,r))+1;
    return ret;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0,n-1));
}

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

www.acmicpc.net/problem/3649  

[난이도] Gold4

[유형] 이분탐색

[풀이]

n이 10만이므로 O(n^2)으로 풀수가 없다.

정렬 후 조각을 한개 정한 뒤 이분탐색으로 나머지 조각을 찾아주면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n,x,u=1e7,al,ar;
int main(){
    while(scanf("%d",&x) !=-1){
        bool ok = 0;
        al=ar=0;
        x*=u;
        scanf("%d",&n);
        vector<int> lego(n);
        for(int i=0;i<n;i++) scanf("%d",&lego[i]);
        sort(lego.begin(),lego.end());   
        for(int i=0;i<n;i++){
            int l = lego[i];
            auto it = lower_bound(lego.begin()+i+1,lego.end(),x-l);
            if(it != lego.end() && l+*it==x){
                if(!ok || ar-al < *it-l){
                    ok=1;
                    ar=*it;
                    al=l;
                }                
            }
        }
        if(ar==0) puts("danger");
        else printf("yes %d %d\n",al,ar);
    }
}

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

www.acmicpc.net/problem/16197  

[난이도] Gold4

[유형] BFS

[풀이]

두 동전의 위치를 기준으로 메모제이션하는 방식의 BFS로 풀면된다.

#include <cstdio>
#include <queue>
using namespace std;
int N,M,cy[2],cx[2],dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
int visit[20][20][20][20];
char map[20][20];
struct P{
    int ay,ax,by,bx;
};
int move(int y,int x){
    if(y<0||x<0||y>=N||x>=M) return -1; 
    if(map[y][x]=='#') return 0;
    return 1;
}
int main(){
    scanf("%d%d",&N,&M);
    cy[0]=-1;
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) {
            scanf(" %c",&map[i][j]);
            if(map[i][j]=='o') {
                if(cy[0]==-1) cy[0]=i,cx[0]=j;
                else cy[1]=i,cx[1]=j;
                map[i][j]='.';
            }
        }
    visit[cy[1]][cx[1]][cy[0]][cx[0]]=visit[cy[0]][cx[0]][cy[1]][cx[1]]=1;
    queue<P> q;
    q.push({cy[0],cx[0],cy[1],cx[1]});
    int cnt=0;
    while(1){
        int sz = q.size();
        if(cnt++==10) break;
        while(sz--){
            P qf = q.front(); q.pop();
            for(int i=0;i<4;i++){   
                P n = qf;
                int ty = qf.ay+dy[i], tx=qf.ax+dx[i];
                int r1 = move(ty,tx);
                if(r1==1) n.ay=ty, n.ax=tx;
                
                ty = qf.by+dy[i], tx=qf.bx+dx[i];
                int r2 = move(ty,tx);
                if(r2==1) n.by=ty, n.bx=tx;
                if(r1==-1 && r2>=0 || r2==-1&&r1>=0) {
                    printf("%d",cnt);
                    return 0;
                }else if(r1+r2==-2 
                || visit[n.ay][n.ax][n.by][n.bx] || visit[n.by][n.bx][n.ay][n.ax]) continue; 

                q.push({n.ay,n.ax,n.by,n.bx});
                visit[n.by][n.bx][n.ay][n.ax] = visit[n.ay][n.ax][n.by][n.bx] = 1;
            }
        }
    }
    puts("-1");
}

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

www.acmicpc.net/problem/8980  

[난이도] Gold4

[유형] Greedy

[풀이]

어떤 마을에 도착했을 때 트럭에 실려있으면서 그마을이 목적지로 되어있는 택배는 모두 내리면 되므로

실을 때 어떻게 실어야 최적이 되는지만 생각하면 된다.

=> Greedy

=> 가장 빨리 내릴 수 있는 택배를 가장 많이 싣고 있는 것이 최적이다.

1. 각 마을에서 택배를 실을 때, 현재 택배를 실고있는 마을에서 가장 가까운 마을부터 택배를 싣는다.

   ex) 현재 마을이 i라면 목적지가 i+1 ~ N 순서로 택배를 차례로 싣는다.

2. 만약 i+1,i+2...j-1 번 마을이 도착지인 택배는 다실었는데 j번째를 싣다가 C를 초과하게 되면

   현재 최적이 되는 것을 방해하고 있는 택배들이 있는지 확인하고 그 택배들을 빼고 대신 j를 실어야 한다.

   제일먼저 빼야하는 택배(가장 비효율적인 택배) 들은 N 마을이 도착지인 택배들이다.

   => N~j+1 마을이 도착지인 택배들을 순서대로 확인하면서 있으면 그 택배들을 빼주고 j번 택배를 싣는다.

#include <cstdio>
#include <cstring>
int N,C,M,dest[2001][2001],cnt[2001],ans;
int main(){
    scanf("%d%d%d",&N,&C,&M);
    while(M--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        dest[a][b]=c;
    }
    int t = 0;
    for(int i=1;i<=N;i++){
        ans+=cnt[i];
        t-=cnt[i];
        for(int j=i+1;j<=N;j++){
            if(!dest[i][j]) continue;
            if(t+dest[i][j]<=C){
               cnt[j]+=dest[i][j];
               t+=dest[i][j];
            }else{
               cnt[j]+=C-t; 
               dest[i][j]-=C-t;
               t = C;               
               for(int k=N;k>j;k--){
                   if(!dest[i][j]) break;
                   if(cnt[k] > 0){
                       if(dest[i][j]<=cnt[k]){
                           cnt[j]+=dest[i][j];
                           cnt[k]-=dest[i][j];
                           dest[i][j]=0;
                       }else{
                           cnt[j]+=cnt[k];
                           dest[i][j]-=cnt[k];
                           cnt[k]=0;
                       }
                   }
               }
            }
        }
    }
    printf("%d",ans);
}

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

www.acmicpc.net/problem/1563  

[난이도] Gold4

[유형] DP

[풀이]

DP[n][l][a] : 현재 n일이고 총 l일 지각했고, a일 연속으로 결석한 상태일 때 N일까지 개근할 수 있는 경우의 수.

점화식 => DP[n][l][a] = DP[n+1][l][0]      출석한 경우

                      + DP[n+1][l+1][0]    지각한 경우 (a가 연속되지 않으므로 초기화)

                      + DP[n+1][l][a+1]    결석한 경우 (l은 연속되지 않아도 되므로 유지하고 a+1)

#include <cstdio>
#include <cstring>
int N,dp[1001][4][4],mod=1000000;
int sol(int n,int l,int a){
    if(l==2 || a==3) return 0;
    if(n==N) return 1;
    int& ret =dp[n][l][a];
    if(ret!=-1) return ret;
    return ret = (sol(n+1,l,0)+sol(n+1,l+1,0)+sol(n+1,l,a+1))%mod;
}
int main(){
    scanf("%d",&N);
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0,0,0));
}

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

www.acmicpc.net/problem/10986

[난이도] Gold4
[유형] 누적합

[풀이]
(i,j) 구간합이 M으로 나누어 떨어지는 경우는
sum(1,j)%M == sum(1,i-1)%M 인 경우이다.

a[1]+a[2]...a[i-1]+a[i]+a[i+1]....a[j]

왜냐하면 j까지의 합이 위와 같고
만약 sum(1,i-1)%M가 k 일때, sum(1,j)%M도 k이려면
sum(i,j)%M은 0이어야 한다.

결국 정답은 나머지가 똑같은 누적합 중에서 두개를 뽑는 경우의 수이다.

#include <cstdio>
int N,M,cnt[1001],sum[1000001];
long long ans;
int main(){
    scanf("%d%d",&N,&M);
    cnt[0]++;
    for(int i=1;i<=N;i++) {
        int v;
        scanf("%d",&v);
        sum[i] = (sum[i-1]+v)%M;
        cnt[sum[i]]++;
    } 
    for(int i=0;i<M;i++){
        int n = cnt[i];
        if(n>1) ans+= ((long long)n*(n-1))/2;
    }
    printf("%lld",ans);
}

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

www.acmicpc.net/problem/13459

[난이도] Gold4

[유형] BFS (삼성SW기출)

[풀이]

맵에 빨간공(R)과 파란공(B)가 있을 때 상하좌우로 기울여서 R을 구멍

O로 10회 이하만에 넣을 수 있는지를 묻는 문제이다.

B가 구멍에 들어가면 실패이며, R과 B가 동시에 들어가도 실패이다.

풀이과정

1. 10초 이하로 할 수 있는지 체크하는 문제

2. n번의 기울임으로 R,B가 특정 위치(ry,rx) ,(by,bx)에 처음으로 도달하는 경우가 생겼을 때

   다른 경로로 n번 이상의 기울임으로 올 수 있는 경우는 생각할 필요가 없다.

   어떤 경로로 왔는지와 상관없이 가장 적은 기울임으로 도착했을 때가 무조건 최적이다.

=> 1,2를 종합해보면 BFS가 적합하다. visit[ry][rx][by][bx] 로 체크.

3. 각 시행마다 4방향씩 기울여보며 시뮬레이션을 해야한다.

   (R,B 좌표를 비교해가며 4방향 각각 시뮬레이션 로직을 구현하면 99% 버그가 생기므로

   이런 문제는 무조건 효율적인 방법을 먼저 생각해야한다.)

4. 각 방향마다 구현하지 않기 위해서 dy[4],dx[4] 배열로 4방향에 대한 값을 정의해놓고 이용한다.

5. i:0~3 방향으로 R,B를 굴려본다.

   [B부터 굴린다.]

   1) B를 먼저 굴려서 O를 만나게 되면 무조건 실패이다. (굴러가는중에 앞에 R이 막고있더라도 R이 먼저 O를 통해 빠져나갈 것이므로 R의 위치와 상관없이 위의 경우는 무조건 실패 케이스이다.)

   2) B를 굴리면서 O를 안만난 경우, 굴러간 경로에 R을 만났는지를 체크하고, 벽을 만나면 멈춘다.

   3) 만나는 중에 R을 만났다면 멈춘 위치에서 -dy[i], -dx[i]한 위치가 다음 B의 위치다. 만약 R을 만났다면 벽에는 R이

      붙어있을 것이므로 -2*dy[i],-2dx[i] 한 좌표가 다음 B의 취이다.

   [R을 굴린다.]

   1) R을 굴리다 O를 만나면 정답을 찾은 것이다. 1을 출력하고 종료하면 된다.

      (B가 동시에 들어가는 B부터 굴리면서 체크했기 때문에 고려할 필요가 없다.)

   B를 굴릴 때 2),3)과 같이 R도 굴려준다.

   새로운 R,B의 위치를 visit 배열에 체크하고 Queue에 넣는다.

6. k번째까지 했는데 답이 안나왔으면 답이 없는 것이므로 0을 출력하고 return.

#include <cstdio>
#include <queue>
using namespace std;
struct P{
    int ry,rx,by,bx;
};
int N,M;
bool visit[11][11][11][11];
char map[11][11];
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,1,-1};
int main(){
    scanf("%d%d",&N,&M);
    P p;
    for(int i=0;i<N;i++) 
        for(int j=0;j<M;j++) {
            scanf(" %c",&map[i][j]);
            if(map[i][j]=='R') {
                p.ry=i,p.rx=j;
                map[i][j]='.';
            }
            else if(map[i][j]=='B') {
                p.by=i,p.bx=j;
                map[i][j]='.';
            }
        }
    queue<P> q;
    q.push(p);
    visit[p.ry][p.rx][p.by][p.bx] = 1;
    int k =0;
    while(!q.empty()){
        if(k==10) break;
        int sz = q.size();
        while(sz--){
            P p = q.front(); q.pop();
            for(int i=0;i<4;i++){
                int nby,nbx,nry,nrx;
                int ty=p.by+dy[i],tx=p.bx+dx[i];
                int meet = 0;
                while(map[ty][tx] !='#' && map[ty][tx] != 'O') {
                    if(ty==p.ry&&tx==p.rx) meet = 1;
                    ty+=dy[i],tx+=dx[i];
                }
                if(map[ty][tx]=='O') continue;
                ty-=(1+meet)*dy[i],tx-=(1+meet)*dx[i];
                nby = ty, nbx = tx;
                
                ty=p.ry+dy[i],tx=p.rx+dx[i];
                meet = 0;
                while(map[ty][tx] !='#' && map[ty][tx] != 'O') {
                    if(ty==p.by&&tx==p.bx) meet = 1;
                    ty+=dy[i],tx+=dx[i];
                }          
                if(map[ty][tx]=='O') {
                    puts("1");
                    return 0;
                }
                ty-=(1+meet)*dy[i],tx-=(1+meet)*dx[i];
                nry = ty, nrx = tx;       

                if(!visit[nry][nrx][nby][nbx]){
                    visit[nry][nrx][nby][nbx]=1;
                    q.push({nry,nrx,nby,nbx});
                }
            }
        }
        k++;
    }
    puts("0");
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/13459.cpp