[백준 20055번 C/C++] 컨베이어 벨트 위의 로봇

 

[백준 20055번 C/C++] 컨베이어 벨트 위의 로봇

 

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

 

---

 

 

해결전략

 

구현, 브루트 포스 Brute Force

 

---

 

 

정답코드

 

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

int n, k;   // n: 컨베이어 길이, k: 내구도가 0인 칸의 개수 한계수
int answer; // 몇 번째 단계인가
deque<pair<int, bool>> dQ; // 내구도, 로봇 배치 여부

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> k;

    for (int i = 0; i < 2 * n; i++) {
        int input;
        cin >> input;
        dQ.push_back({ input, false });
    }

    while (true) 
    {
        answer++;

        // 1. 벨트 회전
        dQ.push_front(dQ.back());
        dQ.pop_back();

        // 로봇이 내려가는 위치(n-1)에서 로봇을 내려야 한다.
        if (dQ[n - 1].second) {
            dQ[n - 1].second = false;
        }

        // 2. 로봇 이동
        for (int i = n - 2; i >= 0; i--) 
        {
            // 현재 위치에 로봇이 있음 && 다음 위치에 로봇 없음 && 다음 위치에 내구도 > 0
            if (dQ[i].second && false == dQ[i + 1].second && dQ[i + 1].first > 0) 
            {
                dQ[i].second = false;    // 로봇 이동 후 i번째 위치에 없으니 false
                dQ[i + 1].second = true; // 로봇 이동 후 i+1번째 위치에 있으니 true
                dQ[i + 1].first--;       // 내구도--

                if (dQ[i + 1].first == 0) k--; // 만약 내구도가 0이 되었다면 k--
            }
        }

        // 로봇이 내려가는 위치(n-1)에서 로봇을 내려야 한다.
        if (dQ[n - 1].second) {
            dQ[n - 1].second = false;
        }

        // 3. 첫 번째 위치에 로봇 올리기
        if (dQ[0].first > 0) {
            dQ[0].second = true; // 0번째 위치에 로봇 올리기
            dQ[0].first--;       // 내구도--

            if (dQ[0].first == 0) k--; // 만약 내구도가 0이 되었다면 k--
        }

        // 4. 내구도가 0인 칸이 k개 이상이면 종료
        if (k <= 0) break;
    }

    cout << answer;

    return 0;
}

 

 

내구도가 음수가 될 수 있으니 

if (dQ[i + 1].first == 0) k--;

다음과 같이 체크해도 중복체크되지 않는다. 

---