20055번 컨베이어 벨트 위의 로봇

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

구현 시뮬레이션

삼성 2020 하반기 신입사원 공채 SW 역량테스트 오전 1번

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 1010
 
int n, k, a[Max];
bool robot[Max];
 
bool chk()
{
    int cnt = 0;
    for (int i = 1; i <= 2 * n; i++)
        if (a[i] == 0)
            ++cnt;
    return cnt >= k ? true : false;
}
 
void move()
{
    int temp = a[2 * n];
 
    for (int i = 2*n; i >= 2 ; i--) {
        a[i] = a[i - 1];
    }
 
    a[1] = temp;
}
 
int simulation() 
{
    int ret = 1, idx= 1;
 
    vector<pair<int, int> > v;
 
    while (true)
    {
        // 순서 1번 수행(벨트 이동)
        move();    
 
        // 순서 1번을 수행하면 자동적으로 벨트 위에 있는 로봇 이동
        for (auto &p : v) {
            robot[p.second] = false;
            if(p.second + 1 != n) robot[p.second + 1] = true; // n+1이 n이라면 어차피 로봇을 내려줄 것이므로 굳이 true로 표시 안 함
            ++p.second;
        }
 
        // n칸에 있는 로봇을 내려줌
        vector<pair<int, int> > vp;
        for (auto &p : v) {
            if (p.second < n) {
                vp.push_back(p);
            }
        }
 
        // 대입
        v = vp;
 
        // 로봇을 올릴 준비
        if (a[1]) {
            // 만약 1번 째 칸의 내구도가 1이상이라면
            v.push_back({ idx, 0 }); // 0이라고 한 것은 아래 for문에서 p.second + 1로 활용할 것이기 때문
            // 그리고 robot[1]을 비교 안 해주는 것은 어차피 1번 째 칸에서 로봇이 있는 경우는 없다. (2n번 째 칸에서 1번 째 칸으로 로봇이 올 수 없기 때문.)
        }    
        
        // 가장 먼저 벨트에 올라간 로봇부터 수행하기 위해 정렬
        sort(v.begin(), v.end());
 
        // vp는 다시 활용할 것이므로, clear
        vp.clear();
 
        // 순서 2번 수행(이동 가능 검사 후 이동)
        for (auto p : v) {
            // 다음 칸에 있는 내구도가 1 이상이고, 그 칸(현재의 다음 칸)에 로봇이 없다면
            if (a[p.second + 1] >= 1 && !robot[p.second + 1]) {
                --a[p.second + 1]; // 내구도 1 감소
                robot[p.second] = false; // 다음 칸으로 이동할 것이기 때문에 현재 칸에는 false 표시
                if (p.second + 1 != n) {
                    // 만약 다음 칸이 n이 아니라면
                    robot[p.second + 1] = true; // 로봇 존재 표시
                    vp.push_back({ p.first, p.second + 1 }); // vp에 넣음
                }
            }
            else {
                // 이동할 수 없으면 가만히 있는다
                vp.push_back({ p.first, p.second});
            }
        }
 
        if (chk()) {
            return ret;
        }
        
        v = vp;
 
        ++ret;
        ++idx;
    }
 
    return ret;
}
 
int main(void)
{
    cin.tie(0);
 
    scanf("%d %d", &n, &k);
 
    for (int i = 1; i <= 2 * n; i++) {
        scanf("%d", &a[i]);
    }
 
    printf("%d\n", simulation());
 
    return 0;
}