프로그래밍

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

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

[풀이]
문제의 주어진 조건대로 시뮬레이션 해주면 됩니다.

#include <cstdio>
int N,a[101],k;

void sol1(int n){
    for(int i=n;i<=N;i+=n){
        a[i]=1-a[i];
    }
}
void sol2(int n){
    int k=0;
    for(int i=1;i<=N/2;i++){
        if(n-i<1||n+i>N||a[n-i]!=a[n+i]) break;
        k=i;
    }
    for(int i=n-k;i<=n+k;i++){
        a[i]=1-a[i];
    }
}

int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&a[i]);
    scanf("%d",&k);
    while(k--){
        int p,m;
        scanf("%d%d",&p,&m);
        if(p==1){
            sol1(m);
        }else{
            sol2(m);
        }
    }
    for(int i=1;i<=N;i++){
        printf("%d ",a[i]);
        if(i%20==0) puts("");
    }
}

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

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

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

[풀이]
구현능력을 보는 시뮬레이션 문제입니다.
풀이법이랄게 딱히 없으며 주어진 조건에 맞게 구현해주면 됩니다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N,K,board[14][14];
int dy[4]={0,0,-1,1};
int dx[4]={1,-1,0,0};
struct P{
    int num,d;
};
pair<int,int> pos[11];
vector<P> horse[14][14];
int cd(int d){
    return d%2==0 ? d+1 : d-1;
} 
bool move(int c,int y,int x,vector<P> v,int d){
    v[0].d=d;
    if(c==1) reverse(v.begin(),v.end());
    for(auto p : v) {
        horse[y][x].push_back(p);
        pos[p.num]={y,x};
    }
    return (int)horse[y][x].size()>=4;
}
int main(){
    scanf("%d%d",&N,&K);
    for(int i=0;i<=N+1;i++){
        for(int j=0;j<=N+1;j++) {
            if(i==N+1||j==N+1||i==0||j==0) board[i][j]=2;
            else scanf("%d",&board[i][j]);
        }
    }
    for(int i=1;i<=K;i++){
        int y,x,d;
        scanf("%d%d%d",&y,&x,&d);
        horse[y][x].push_back({i,d-1});
        pos[i]={y,x};
    }
    for(int ans=1;ans<=1000;ans++){
        for(int k=1;k<=K;k++){
            auto [y,x] = pos[k];
            int d,idx;
            vector<P> tmp;
            for(int i=0;i<horse[y][x].size();i++){
                if(horse[y][x][i].num==k){
                    idx=i;
                    d=horse[y][x][i].d;
                    break;
                }
            }
            for(int i=idx;i<horse[y][x].size();i++) tmp.push_back(horse[y][x][i]);
            horse[y][x].erase(horse[y][x].begin()+idx,horse[y][x].end());

            int ny=y+dy[d],nx=x+dx[d];
            bool ret=0;
            if(board[ny][nx]==2) {
                d=cd(d);
                int nny=y+dy[d],nnx=x+dx[d];   
                if(board[nny][nnx]==2) ret=move(0,y,x,tmp,d);
                else ret=move(board[nny][nnx],nny,nnx,tmp,d);

            }else{
                ret=move(board[ny][nx],ny,nx,tmp,d);
            }
            if(ret) {
                printf("%d",ans);
                return 0;
            }
        }
    }
    puts("-1");
}

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

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

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

[풀이]
주사위가 동서남북 방향으로 움직일 때, 각각 주사위 면의 원소들이 어떻게 이동하게 되는지를
미리 함수에 정의해고 조건에 맞게 시뮬레이션을 해주면 됩니다.

#include <cstdio>
#include <cstring>
using namespace std;
int N,M,K,board[22][22],dice[7]={0,1,2,3,4,5,6},visit[22][22];
int dy[4]={0,1,0,-1};
int dx[4]={1,0,-1,0};
void move(int d){
    int tmp[7];
    for(int i=1;i<=6;i++) tmp[i]=dice[i];
    if(d==0){
        dice[1]=tmp[4];
        dice[3]=tmp[1];
        dice[4]=tmp[6];
        dice[6]=tmp[3];
    }else if(d==1){
        dice[1]=tmp[2];
        dice[2]=tmp[6];
        dice[5]=tmp[1];
        dice[6]=tmp[5];
    }else if(d==2){ 
        dice[1]=tmp[3];
        dice[4]=tmp[1];
        dice[3]=tmp[6];
        dice[6]=tmp[4];
    }else{
        dice[1]=tmp[5];
        dice[2]=tmp[1];
        dice[5]=tmp[6];
        dice[6]=tmp[2];
    }
}
int dfs(int y,int x){
    visit[y][x]=1;
    int ret=1;
    for(int i=0;i<4;i++){
        int ny=y+dy[i],nx=x+dx[i];
        if(board[ny][nx] && board[ny][nx]==board[y][x] && !visit[ny][nx]){
            ret+=dfs(ny,nx);
        }
    }
    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",&board[i][j]);
    int d=0,cy=1,cx=1,ans=0,cnt=0;;
    while(K--){
        int ny=cy+dy[d],nx=cx+dx[d];
        if(!board[ny][nx]){
            d=(d+2)%4;
            K++;
            continue;
        }
        move(d);
        if(dice[6]>board[ny][nx]) d=(d+1)%4;
        else if(dice[6]<board[ny][nx]) d=(d+3)%4;
        ans+=dfs(ny,nx)*board[ny][nx];
        memset(visit,0,sizeof(visit));
        cy=ny,cx=nx;
    }
    printf("%d",ans);
}

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

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

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

[풀이]
set 2개를 이용해 현재 빈자리와 현재 사용중인 자리를 저장해주면서
시뮬레이션을 해주었습니다. 삽입/삭제를 O(logN)에 할 수 있도록 set을 이용하였습니다.
우선순위 큐를 이용하여도 됩니다.

#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
int N,pos[100001],cnt[100001];
vector<pair<int,int>> v;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        int s,e;
        scanf("%d%d",&s,&e);
        v.push_back({s,i});
        v.push_back({e,i});
    }
    set<int> empty,use;
    sort(v.begin(),v.end());
    for(auto [t,i] : v){
        if(pos[i]){
            use.erase(pos[i]);
            empty.insert(pos[i]);
        }else{
            if(empty.size()>0){
                pos[i]=*empty.begin();
                empty.erase(pos[i]);
            }else if(use.size()>0){
                pos[i]=*(--use.end())+1;
            }else{
                pos[i]=1;
            }
            use.insert(pos[i]);
            cnt[pos[i]]++;
        }
    }
    vector<int> ans;
    for(int i=1;;i++){
        if(!cnt[i]) break;
        ans.push_back(cnt[i]);
    }
    printf("%d\n",ans.size());
    for(auto a : ans) printf("%d ",a

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

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

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

[풀이]
우선 토네이도의 규칙성을 파악해야 합니다.
<-,ㅜ,->,ㅗ 방향을 각각 0,1,2,3 이라고 정하고
격자의 크기가 N일 때, (N/2+1,N/2+1) 에서부터
0->1->2->3->0 순서로 방향을 바꾸며 진행됩니다.
각 방향으로 진행하는 횟수는 1,1,2,2,3,3,4,4....N-1,N-1,N-1 로
방향이 2회 바뀔때마다 횟수가 1번씩 늘어나며 마지막 N-1번 진 행할때는 3번 방향이 바뀝니다.

위를 이용해 시뮬레이션을 해주면 되는데

map<int,vector<pair<int,int>>> table =
{
    {1,{{1,1},{-1,1}}},
    {2,{{2,0},{-2,0}}},
    {7,{{1,0},{-1,0}}},
    {10,{{1,-1},{-1,-1}}},
    {5,{{0,-2}}}
};

위와 같이 현재 방향이 0일때의 {퍼센트,{토네이도로부터의 상대좌표}} 들을 map을 이용해 저장해 놓고
시계방향으로 90도 회전할때마다 (y,x) -> (-x,y)로 좌표들을 변경해서 이용해주면 됩니다.
즉, 방향이 0일때는 0번, 1일때는 1번, 2일때는 2번, 3일때는 3번 회전시켜주면 되므로
위의 1개의 테이블만 정의해주면 됩니다.

#include <map>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
int N,board[501][501],ans;
int dy[4] = {0,1,0,-1};
int dx[4] = {-1,0,1,0};
map<int,vector<pair<int,int>>> table = 
{
    {1,{{1,1},{-1,1}}},
    {2,{{2,0},{-2,0}}},
    {7,{{1,0},{-1,0}}},
    {10,{{1,-1},{-1,-1}}},
    {5,{{0,-2}}}
};
pair<int,int> cvt(int dir,int y,int x){
    for(int i=0;i<dir;i++) {
        int ny=-x,nx=y;
        y=ny,x=nx;
    }
    return {y,x};
}
void update(int dir,int fy,int fx){
    int total=board[fy][fx];
    int erased=0;
    for(auto [k,v] : table){
        for(auto p : v){
            auto c = cvt(dir,p.first,p.second);
            int ny=fy+c.first, nx=fx+c.second;
            int r = total*(k/100.0);
            erased+=r;
            if(ny>=1&&nx>=1&&ny<=N&&nx<=N) board[ny][nx]+=r;
            else ans+=r;
        }
    }
    board[fy][fx]=0;
    int ty=fy+dy[dir],tx=fx+dx[dir];
    if(ty>=1&&tx>=1&&ty<=N&&tx<=N) board[ty][tx]+=total-erased;
    else ans+=total-erased;
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) scanf("%d",&board[i][j]);
    int cy=N/2+1,cx=N/2+1,dir=0;
    for(int i=1;i<N;i++){
        int cnt=2;
        if(i==N-1) cnt=3;
        for(int j=0;j<cnt;j++){
            for(int k=0;k<i;k++){
                cy+=dy[dir];
                cx+=dx[dir];
                update(dir,cy,cx);
            }
            dir=(dir+1)%4;
        }
    }
    printf("%d",ans);
}

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

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=581&sw_prbl_sbms_sn=16912

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

[풀이]
레일의 최대 개수가 N밖에 안되므로 next_permutation을 이용하면 모든 레일 순서를 구할 수 있습니다.
각 순서마다 문제의 조건에 맞게 시뮬레이션 하면 들어야 하는 무게의 최솟값을 구할 수 있습니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int N,M,K,a[10],ans=9e8;
int main(){
    scanf("%d%d%d",&N,&M,&K);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    sort(a,a+N);
    do{
        int cur=0, work=0;
        for(int i=0;i<K;i++){
            int r = M;
            while(1){
                r-=a[cur];
                if(r<0) break;
                work+=a[cur++];
                cur%=N;
            }
        }
        ans=min(ans,work);
    }while(next_permutation(a,a+N));
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/택배_마스터_광우.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