프로그래밍

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

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

[풀이]
문제의 조건대로 시뮬레이션을 해준다.
배열이 덮어씌워지는 실수를 하지 않기 위해 2차원 vector를 생성해주며 답을 구해주면 편하다.

#include <cstdio>
#include <vector>
using namespace std;
using vvi = vector<vector<int>>;
int dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
int R,C,T,up=-1;
vvi sol(vvi A){
    vvi ret(R,vector<int>(C));
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            if(A[i][j]>0){
                int cnt=0;
                int d = A[i][j]/5;
                for(int k=0;k<4;k++){
                    int ny=i+dy[k],nx=j+dx[k];
                    if(ny<0||nx<0|ny>=R||nx>=C||A[ny][nx]==-1) continue;
                    ret[ny][nx]+=d;
                    cnt++;
                }           
                ret[i][j]+=A[i][j]-cnt*d;
            }
        }
    }
    vvi ret2 = ret;
    for(int i=2;i<C;i++) {
        ret2[up][i] = ret[up][i-1];
        ret2[up+1][i] = ret[up+1][i-1];
    }
    for(int i=C-2;i>=0;i--) {
        ret2[0][i] = ret[0][i+1];
        ret2[R-1][i] = ret[R-1][i+1];
    }
    for(int i=up-1;i>=0;i--) ret2[i][C-1] = ret[i+1][C-1];
    for(int i=1;i<=up;i++) ret2[i][0] = ret[i-1][0];
    for(int i=up+2;i<R;i++) ret2[i][C-1] = ret[i-1][C-1];
    for(int i=R-2;i>=up+1;i--) ret2[i][0] = ret[i+1][0];
    ret2[up][0]=ret2[up+1][0]=-1;
    ret2[up][1]=ret2[up+1][1]=0;
    return ret2;
}
int main(){
    scanf("%d%d%d",&R,&C,&T);

    vvi A(R,vector<int>(C));
    for(int i=0;i<R;i++)
        for(int j=0;j<C;j++) {
            scanf("%d",&A[i][j]);
            if(A[i][j]==-1){
                if(up==-1) up=i;
            }
        }

    while(T--) A=sol(A);
    
    int ans=0;
    for(int i=0;i<R;i++)
        for(int j=0;j<C;j++)
            if(A[i][j]>0) ans+=A[i][j];

    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/17144.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

www.acmicpc.net/problem/19238

[난이도] Gold4

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

[풀이] 

1. y시작,x시작,y종료,x종료,현재 택시위치에서의 거리 d 이 5가지를 저장하는
구조체 P를 정의한다.
2. vector<P> s를 정의 M개의 P를 저장한다.
3. M회 루프를 돌면서 매 시행마다 s를 정렬해준다. 정렬은 comparator 를
   재정의하는 방식으로 한다. 거리,y좌표,x 우선순위로 정렬하면 항상
   s[0]이 지금 태우러 가야하는 사람이다. 뽑은 뒤 s[0]은 필요없으므로
   벡터에서 지워준다.
4. 벽에 의해 택시로 도달할 수 없는 사람이 있는 겨우와, 연료를 다쓰는 경우를
   예외처리 해준다.

#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
struct P{
    int y,x,ey,ex,d;
};
vector<P> s;
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,1,-1};
int N,M,K,map[21][21],py,px,INF=9e8;
bool visit[21][21];
int bfs(int y,int x){
    memset(visit,0,sizeof(visit));
    queue<P> q;
    q.push({y,x});
    visit[y][x] = 1;
    int ret = 0;
    while(!q.empty()){
        int sz = q.size();
        while(sz--){
            P qf = q.front(); q.pop();
            if(qf.y==py&&qf.x==px) return ret;
            for(int i=0;i<4;i++){
                int ny = qf.y+dy[i];
                int nx = qf.x+dx[i];
                if(ny < 1 || nx < 1 || ny > N || nx > N || map[ny][nx]) continue;
                if(!visit[ny][nx]){
                    q.push({ny,nx});
                    visit[ny][nx] = 1;
                }
            }
        }
        ret++;
    }
    return INF;
}
bool cmp(P& a,P& b){
    if(a.d < b.d) return 1;
    else if(a.d==b.d){
        if(a.y<b.y) return 1;
        else if(a.y==b.y) return a.x < b.x;
        return 0;
    }
    return 0;
}
int main(){
    scanf("%d%d%d",&N,&M,&K);
    s.resize(M);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) scanf("%d",&map[i][j]);
    
    scanf("%d%d",&py,&px);
    for(int i=0;i<M;i++) scanf("%d%d%d%d",&s[i].y,&s[i].x,&s[i].ey,&s[i].ex);

    for(int i=0;i<M;i++){
        for(int j=0;j<s.size();j++) s[j].d = bfs(s[j].y,s[j].x);    
        sort(s.begin(),s.end(),cmp);
        P t = s[0];
        s.erase(s.begin());
        if(K-t.d < 0) {
            K=-1;
            break;
        }
        K-=t.d, py=t.y, px=t.x;

        int nDist = bfs(t.ey,t.ex);
        if(K-nDist < 0){
            K=-1;
            break;
        }
        py=t.ey, px=t.ex;
        K+=nDist;
    }
    printf("%d",K);
}

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

www.acmicpc.net/problem/17779

[난이도] Gold4

[유형] Brute force, DFS (삼성SW기출)

[풀이]

1. 문제의 주어진 조건에 따라 5선거구의 경계를 체크한다.

2. (1,1)은 1선거구, (1,N)은 2선거구, (N,1)은 3선거구 (N,N)은 4선거구에 각각 무조건 포함되므로 4개의 점에서 DFS를 수행하면서 각 선거구의 인구를 구한다.

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int N,map[21][21],A[21][21],total,ans=1e8;
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,1,-1};
bool check(int d1,int d2,int x,int y){
    bool r = d1 >= 1 && d2 >= 1 && 1 <= x && x < x+d1+d2 && x+d1+d2 <= N;
    bool c = 1 <= y-d1 && y-d1 < y && y < y+d2 && y+d2 <=N;
    return r&&c;
}
void mask(int d1,int d2,int x,int y){
    int sx,sy,dx,dy;

    sx=x,sy=y,dx=1,dy=-1;
    for(int i=0;i<=d1;i++) {
        map[sx][sy] = 1;
        sx+=dx,sy+=dy;
    }
    sx=x,sy=y,dx=1,dy=1;
    for(int i=0;i<=d2;i++) {
        map[sx][sy] = 1;
        sx+=dx,sy+=dy;
    }
    sx=x+d1,sy=y-d1,dx=1,dy=1;
    for(int i=0;i<=d2;i++) {
        map[sx][sy] = 1;
        sx+=dx,sy+=dy;
    }  
    sx=x+d2,sy=y+d2,dx=1,dy=-1;
    for(int i=0;i<=d1;i++) {
        map[sx][sy] = 1;
        sx+=dx,sy+=dy;
    }     
}

int dfs(int d1,int d2,int x,int y,int r,int c,int k){
    if(k==1){
        if(!(1<=r&&r<x+d1&&1<=c&&c<=y)) return 0;
    }else if(k==2){
        if(!(1<=r&&r<=x+d2&&y<c&&c<=N)) return 0;
    }else if(k==3){
        if(!(x+d1<=r&&r<=N&&1<=c&&c<y-d1+d2)) return 0;
    }else if(k==4){
        if(!(x+d2<r&&r<=N&&y-d1+d2<=c&&c<=N)) return 0;
    }
    map[r][c] = k;
    int ret = A[r][c];
    for(int i=0;i<4;i++){
        int nr = r+dx[i];
        int nc = c+dy[i];
        if(nr < 1 || nc < 1 || nr > N || nc > N || map[nr][nc]) continue; 
        ret += dfs(d1,d2,x,y,nr,nc,k);
    }
    return ret;
}

int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) {
            scanf("%d",&A[i][j]);
            total+=A[i][j];
        }

    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            for(int d1=1;d1<=N;d1++){
                for(int d2=1;d2<=N;d2++){
                    if(!check(d1,d2,i,j)) continue;
                    memset(map,0,sizeof(map));
                    mask(d1,d2,i,j);
                    int sx = 1,sy=1;
                    vector<int> sum;
                    sum.push_back(dfs(d1,d2,i,j,1,1,1));
                    sum.push_back(dfs(d1,d2,i,j,1,N,2));
                    sum.push_back(dfs(d1,d2,i,j,N,1,3));
                    sum.push_back(dfs(d1,d2,i,j,N,N,4));
                    int rm = total;
                    for(int i=0;i<4;i++) rm -= sum[i];
                    sum.push_back(rm);
                    sort(sum.begin(),sum.end());
                    ans = min(ans,sum.back()-sum.front());
                }
            }
        }
    }    
    printf("%d",ans);
}

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

www.acmicpc.net/problem/17406

[난이도] Gold4

[유형] 시뮬레이션

[풀이]

next_permutation을 이용해 모든 경우의 수를 다해본다. permutation으로 돌아가는것은 index라는 것에 주의.

#include <cstdio>
#include <algorithm>
using namespace std;
int N,M,K,org[51][51],cp[51][51],tmp[51][51],r[6],c[6],s[6],v[6],inf=1e8;
int sol(){
    int ret = inf;
    for(int i=0;i<K;i++){
        int ll = 2*s[v[i]]+1, yy = r[v[i]]-s[v[i]], xx = c[v[i]]-s[v[i]];        
        int l = ll, y = yy, x = xx;
        while(l>0){
            if(l==1) {
                tmp[y][x] = cp[y][x];
                break;
            }
            for(int j=x+1;j<x+l;j++) tmp[y][j] = cp[y][j-1];
            for(int j=y+1;j<y+l;j++) tmp[j][x+l-1] = cp[j-1][x+l-1];
            for(int j=x;j<x+l-1;j++) tmp[y+l-1][j] = cp[y+l-1][j+1];
            for(int j=y;j<y+l-1;j++) tmp[j][x] = cp[j+1][x];
            y++,x++;
            l-=2;
        }
        for(int j=yy;j<yy+ll;j++)
            for(int k=xx;k<xx+ll;k++) cp[j][k] = tmp[j][k];
    }
    for(int i=1;i<=N;i++){
        int sum = 0;
        for(int j=1;j<=M;j++) sum+=cp[i][j];
        ret = min(ret,sum);
    }
    return ret;
}
int main(){
    scanf("%d%d%d",&N,&M,&K);
    for(int i=1;i<=N;i++) 
        for(int j=1;j<=M;j++) scanf("%d",&org[i][j]);

    for(int i=0;i<K;i++) {
        scanf("%d%d%d",&r[i],&c[i],&s[i]);
        v[i] = i;
    }
    int ans = inf;
    do{
        for(int i=1;i<=N;i++) copy(org[i],org[i]+M+1,cp[i]);
        ans =min(ans,sol());
    }while(next_permutation(v,v+K));
    printf("%d",ans);
} 

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

www.acmicpc.net/problem/17281

[난이도] Gold4

[유형] Brute force, Simulation

[풀이] 

next_permutation을 이용해 모든 경우를 다 해보면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N,a[50][9],res;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++)
        for(int j=0;j<9;j++) scanf("%d",&a[i][j]);
    
    vector<int> p = {1,2,3,4,5,6,7,8};
    do{
        vector<int> seq = p;
        seq.insert(seq.begin()+3,0);
        int scr = 0,j=0;
        for(int i=0;i<N;i++){
            vector<bool> pos(3);
            int out=0;
            while(out<3){
                int cmd = a[i][seq[j]];
                if(cmd==0) out++;
                else if(cmd<4){
                    for(int k=2;k>=0;k--){
                        if(pos[k]==1) {
                            int nxt = k+cmd;
                            if(nxt > 2) scr++;
                            else pos[nxt] = 1;
                            pos[k]=0;
                        }     
                    }
                    pos[cmd-1]=1;
                }else {
                    for(int k=2;k>=0;k--){
                        scr+=pos[k];
                        pos[k]=0;
                    }
                    scr++;
                }
                j=(j+1)%9;
            }
        }
        res = max(res,scr);
    }while(next_permutation(p.begin(),p.end()));
    printf("%d",res);
}

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

www.acmicpc.net/problem/17140

[난이도] Gold4

[유형] 시뮬레이션 (삼성SW기출)

[풀이]

R 연산에 대한 함수만 정의하고 배열을 반시계 방향으로 회전하는 함수를 들어서 이용하면 C 연산은 따로 정의하지 않아도 해결할 수 있다.

#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
using vvi = vector<vector<int>>;
int r,c,k;

vvi rot(vvi& m){
    int csz = m.size();
    int rsz = m[0].size();
    vector<vector<int>> ret(rsz,vector<int>(csz));
    for(int i=0;i<rsz;i++)
        for(int j=0;j<csz;j++) ret[i][j] = m[j][rsz-i-1];

    return ret;
}

vvi R(vvi& m){
    vvi tmp;
    int mxl = 0;
    for(auto v : m){
        map<int,int> cntMap;
        for(auto i : v) {
            if(i!=0) cntMap[i]++;
        }

        vector<pair<int,int>> ov;
        for(auto p : cntMap){
            ov.push_back({p.second,p.first});
        }
        sort(ov.begin(),ov.end());
        vector<int> res;
        for(auto o : ov){
            res.push_back(o.second);
            res.push_back(o.first);
        }
        mxl = max(mxl,(int)res.size());
        tmp.push_back(res);
    }
    mxl = min(100,mxl);
    for(auto& t : tmp) t.resize(mxl);
    return tmp;
}

int main(){
    scanf("%d%d%d",&r,&c,&k);
    r--,c--;
    vvi map;
    for(int i=0;i<3;i++){
        vector<int> a(3);
        for(int j=0;j<3;j++) scanf("%d",&a[j]);
        map.push_back(a);
    }
    int time = 0;
    while(1){
        int rsz = map.size();
        int csz = map[0].size();
        if(r < rsz && c < csz && map[r][c]==k) break;
        if(time==100){
            time = -1;
            break;
        }
        if(rsz >= csz){
            map = R(map);
        }else{
            map = rot(map);
            map = R(map);
            for(int i=0;i<3;i++) map=rot(map);
        }
        time++;
    }
    printf("%d",time);
}

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

www.acmicpc.net/problem/17135

[난이도] Gold4

[유형] 시뮬레이션, Brute Force

[풀이]

각 열의 성에서 먼 순서대로 stack에 쌓아서 시뮬레이션하면 편하게 풀수 있다.

#include <cstdio>
#include <stack>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
using namespace std;
int N,M,D,ans,tt,total;
int dist(int sx,int ey,int ex){
    return ey+abs(ex-sx);
}
void fwd(vector<stack<int>>& s){
    for(int i=0;i<s.size();i++){
        stack<int> tmp;
        while(!s[i].empty()){
            tmp.push(s[i].top()-1); 
            s[i].pop();
        }
        while(!tmp.empty()){
            int t = tmp.top(); tmp.pop();
            if(t>0) s[i].push(t);
            else tt--;
        }
    }
}
int main(){
    scanf("%d%d%d",&N,&M,&D);
    vector<stack<int>> st(M);
    for(int i=1;i<=N;i++){
        for(int j=0;j<M;j++){
            int v;
            scanf("%d",&v);
            if(v) {
                st[j].push(N-i+1); 
                total++;
            }
        }
    }
    vector<bool> seq(M);
    for(int i=M-3;i<M;i++) seq[i]=1;
    do{
        vector<int> a;
        for(int i=0;i<seq.size();i++) if(seq[i]) a.push_back(i);

        auto cpst = st;
        int cnt = 0;
        tt = total;
        while(1){
            set<int> rmv;
            for(auto sx : a){
                int mxidx = -1, minv = 1<<9;
                for(int x=0;x<M;x++){
                    if(cpst[x].empty()) continue;
                    int ey = cpst[x].top();
                    int d = dist(sx,ey,x);
                    if(d>D) continue;
                    if(minv > d){
                        mxidx = x;
                        minv = d;
                    }
                }
                if(mxidx!=-1) rmv.insert(mxidx);
            }
            for(auto r : rmv){
                cpst[r].pop();
                cnt++;
                tt--;
            }
            fwd(cpst);
            if(tt==0) break;
        }
        ans = max(ans,cnt);
    }while(next_permutation(seq.begin(),seq.end()));
    printf("%d",ans);
}

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