백준 20055 C++

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

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

 

문제 정리

하 머야

 

생각

벨트를 두 개를 만들어서 관리하는데 배열을 따로 쓸지 2차원 배열을 쓸지 고민이다

로봇 유무는 bool로 확인, 먼저 올라간 로봇 먼저 움직인다 -> 큐를 사용? 뭐가 일케 많음

하 넘 생각할 게 많아

 

코드

#include <iostream>

using namespace std;

int main() {
    int N, K;
    cin >> N >> K;

    int durability[2 * N];
    bool robot[2 * N];

    for (int i = 0; i < 2 * N; ++i) {
        cin >> durability[i];
    }

    for (int i = 0; i < 2 * N; ++i) {
        robot[i] = false;
    }

    int step = 0;
    int zeroCount = 0;

    while (true) {
        int temp = durability[2 * N - 1];
        for (int i = 2 * N - 1; i > 0; --i) {
            durability[i] = durability[i - 1];
        }
        durability[0] = temp;

        for (int i = N - 1; i > 0; --i) {
            robot[i] = robot[i - 1];
        }
        robot[0] = false;
        robot[N - 1] = false;

        for (int i = N - 2; i >= 0; --i) {
            if (robot[i] && !robot[i + 1] && durability[i + 1] > 0) {
                robot[i] = false;
                robot[i + 1] = true;
                durability[i + 1]--;
                if (durability[i + 1] == 0) zeroCount++;
            }
        }
        robot[N - 1] = false;

        if (!robot[0] && durability[0] > 0) {
            robot[0] = true;
            durability[0]--;
            if (durability[0] == 0) zeroCount++;
        }

        if (zeroCount >= K) break;

        step++;
    }
    cout << step + 1 << endl;
}

 

- durability 배열 : 각 위치의 내구도를 저장

- robot 배열 : 각 위치에 로봇이 있는지 여부를 저장

- 배열 크기 :  컨베이어 벨트의 길이의 두 배인 2 * N로 둠

- robot 배열 초기화 : false -> 로봇 없는 상태

 

컨베이어 벨트의 상태를 시뮬레이션 과정

• 1. 벨트 회전!
• 2. 로봇 이동 후 내구도 감소, 로봇이 내구도가 0인 위치에 가면 zeroCount를 증가시킴
• 3. 새로운 로봇을 올리는데 첫 번째 위치 / 내구도가 0이 아닌 경우에만 올리기!
• 4. zeroCount가 K와 같거나 크면 반복문 나오기!

반복문 종료후엔 step+1로 시간 출력

 

while문 자세히 설명해보자면! 

Step 1: 벨트 회전

// Step 1: 벨트 회전
        int temp = durability[2 * N - 1];
        // temp에 마지막 위치의 내구도 값 저장! 
        // 회전이 끝난 후에 첫 번째 위치에 배치할 때 사용됨
        for (int i = 2 * N - 1; i > 0; --i) {
        // 벨트의 각 위치의 내구도를 오른쪽으로 한 칸씩 이동
            durability[i] = durability[i - 1];
            // 현재 위치의 내구도를 바로 오른쪽 위치의 내구도로 바꾸기 (그냥 회전 구현하는 거에요)
        }
        durability[0] = temp;
        // 첫 번째 위치의 내구도를 temp 값으로 바꿈
        // 이렇게 하면 벨트가 회전하는 효과

        for (int i = N - 1; i > 0; --i) {
        // 로봇의 위치도 벨트와 동일하게 오른쪽으로 한 칸씩 이동
            robot[i] = robot[i - 1];
        }
        robot[0] = false;
        robot[N - 1] = false;
        //첫 번째 / 마지막 위치는 로봇이 없는 것으로 처리

- 컨베이어 벨트와 로봇의 상태가 회전되는 효과 구현

 

Step 2: 로봇 움직이기 

// Step 2: 로봇 움직이기
        for (int i = N - 2; i >= 0; --i) {
        // 마지막에서 두 번째 위치부터 시작해서 첫 번째 위치까지 거꾸로 탐색!
        // 로봇이 마지막 위치부터 역순으로 이동할 때 첫 번째 위치까지 이동할 수 있게 하려고
            if (robot[i] && !robot[i + 1] && durability[i + 1] > 0) {
            // 현재 위치에 로봇이 있고 + 그 다음 위치에 로봇이 없고 + 그 다음 위치의 내구도가 0보다 큰 경우 로봇 이동
                robot[i] = false;
                // 현재 위치의 로봇을 제거
                robot[i + 1] = true;
                // 그 다음 위치에 로봇을 추가
                durability[i + 1]--;
                // 그 다음 위치의 내구도를 감소
                if (durability[i + 1] == 0) zeroCount++;
                // 내구도가 0이 되면 zeroCount 증가
                // == 내구도가 0이 된 위치의 로봇은 더 이상 이동할 수 없음
            }
        }
        robot[N - 1] = false;
        // 마지막 위치에 있는 로봇은 이동할 수 없음

 

- 로봇은 내구도가 0이 아니고 오른쪽으로 이동 가능한 경우에만 이동할 수 있음

- 로봇이 한 칸씩 오른쪽으로 이동하면서 내구도를 감소시키는 효과 구현

 

Step 3: 새로운 로봇 올리기

// Step 3: 새로운 로봇 올리기
        if (!robot[0] && durability[0] > 0) {
        // 첫 번째 위치에 로봇이 없고 내구도가 있는 경우에만
            robot[0] = true;
            // 새로운 로봇을 올림
            durability[0]--;
            // 이후 첫 번째 위치의 내구도를 감소
            if (durability[0] == 0) zeroCount++;
            // 위와 같이 내구도가 0이 되면 zeroCount 증가
            // 내구도가 0인 위치에 로봇이 올라가면 이후 로봇은 더 이상 그 위치로 이동할 수 없기 때문에 zeroCount 증가
        }

 

Step 4: 조건 확인 후 탈출!

// Step 4: 조건 확인 후 탈출!
        if (zeroCount >= K) break;
        //내구도가 K 이상 == 충분한 수의 로봇이 내구도가 0인 위치에 도달했다는 것을 의미