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

풀이 시간: 56m01s01(분석) + 1h07m13s92(초기 코드) + 1h01m41s46(오류 수정)

시간 복잡도: O(N)

공간 복잡도: O(N)

문제

입력

첫째 줄에 N, K가 주어진다. 둘째 줄에는 A1, A2, ..., A2N이 주어진다.

출력

몇 번째 단계가 진행 중일때 종료되었는지 출력한다.

문제 풀이

처음에 이 문제를 읽고 20분동안 분석해보았는데, 조금 헷갈리는 부분이 있어 질문 게시판을 참고하여 문제를 좀 더 잘 풀어서 설명해준 글들을 읽고 다시 분석했다.

https://www.acmicpc.net/board/view/116253

https://www.acmicpc.net/board/view/114048

헷갈리는 내용 정리

▪️ 출력에서 말하는 '단계'라는 것은 지문에 나온 1~4번 과정을 하나로 묶은 것을 의미한다. 따라서 1~4번 과정을 모두 거쳐야 1번째 단계인 것이다.

▪️ 처음 시작할 때 로봇이 없는 경우에도 벨트가 회전하기 때문에, 고로 로봇이 없다고 3번부터 시작되진 않는다.

▪️ 1번에서 회전하는 도중에 N번 위치의 벨트 위에 있는 로봇은 바로 삭제된다.

▪️ 1번에서 회전할 때 벨트와 로봇이 함께 움직이므로, 해당 벨트의 내구도도 같이 이동하게 되는 것이다.

▪️ 시작할 때가 1단계이므로, 만약 처음 시작할 때부터 내구도가 0인 칸의 개수가 K개 이상이면 답으로 1을 출력하게 된다.

궁금한 점

만약 한 칸을 이동하게 되면 올리는 위치와 내리는 위치가 고정인것인가? 아니면 같이 이동하는 것인가?

올리는 위치랑 내리는 위치가 1번과 N번 칸으로 아예 고정(파란 글씨)이라 한 칸씩 이동할 때도 올리는 위치 내리는 위치가 함께 이동하는건지, 아니면 올리는 위치랑 내리는 위치가 그냥 그 전체 컨베이어 벨트의 해당 위치들에 고정(초록 글씨)이라 한 칸씩 이동하면 그 이전의 벨트 칸으로 적용되는건지 헷갈린다.

 

일단 본인은 초록색 글씨가 맞다고 생각했기 때문에, 올리는 위치와 내리는 위치의 인덱스 값을 따로 저장하여 계속 이전 위치의 인덱스로 갱신해주기로 했다. 즉, 그림에 따르면 한 칸씩 이동했을 때 올리는 위치는 1에서 2N이 되는 것이고, 내리는 위치는 N에서 N-1이 되는 것이다.

 

편의상 전체 인덱스를 0부터 (2*N-1)까지로 설정하여 진행하였다.

 

처음에는 올리는 위치에서 로봇이 존재하지 않을 경우를 추가하여 문제를 풀었었는데, 답이 전혀 다르게 나왔다. 그래서 문제를 읽고 그냥 내구도를 확인하라는 내용만 있길래 그냥 로봇이 존재하지 않을 경우 조건을 뺐더니 예제 출력이 제대로 나왔다.

요약하자면 그냥 올리는 위치에 로봇이 있든지 말든지 상관 없이 내구도만 확인하면 됐던 것이다.

// 초기 코드
if (!R[up] && A[up] >= 1)

// 다음과 같이 변경
if (A[up] >= 1)

초기 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, K, cnt = 0, up = 0, down;
vector<int> A; // 각 벨트 위치의 내구도
vector<bool> R; // 각 위치별 로봇 유무

void rotateAll() {
    // 전체 회전한다는 것은 올리는 위치와 내리는 위치가 이동한다는 것
    up = up - 1 >= 0 ? up - 1 : 2 * N - 1;
    down = down - 1 >= 0 ? down - 1 : 2 * N - 1;
    R[down] = false; // 내리는 위치의 로봇 제거
}

void rotateRobot() {
    // R를 거꾸로 탐색(가장 먼저 올린 로봇부터 탐색)
    for (int i = 2 * N - 1; i >= 0; --i) {
        int next = (i + 1) % (2 * N - 1); // 다음 위치
        // 현재 위치에 로봇이 있고, 다음 위치에 로봇이 없으며, 다음 위치의 내구도가 1 이상인 경우 로봇 이동
        if (R[i] && !R[next] && A[next] >= 1) {
            R[next] = true;
            R[i] = false;
            A[next]--;
        }
        R[down] = false; // 내리는 위치의 로봇 제거
    }
}

void loadRobot() {
    if (A[up] >= 1) { // 올리는 위치의 내구도가 1 이상인 경우 로봇 올림
        R[up] = true;
        A[up]--;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N >> K;
    down = N - 1; // 내리는 위치 설정
    A = vector<int>(2 * N, 0);
    R = vector<bool>(2 * N, false);
    for (int i = 0; i < 2 * N; ++i) cin >> A[i];

    // 내구도가 0인 칸의 개수가 K개보다 작을 때만 반복
    while (count(A.begin(), A.end(), 0) < K) {
        cnt++; // 단계 먼저 추가
        rotateAll(); // 벨트와 로봇 회전
        if (cnt > 1) rotateRobot(); // 로봇 회전 (첫 번째 단계에서는 로봇이 없으므로 생략)
        loadRobot(); // 로봇 올리기
    }
    cout << cnt;
    return 0;
}

 

처음에 위와 같이 풀었는데, 예제 2번 출력이 제대로 맞게 나오지 않았다.

그래서 다른 정답 코드들과 비교하여 각 A(내구도)와 R(로봇 위치) 벡터를 전부 출력해봤는데, 예제 2번만 다르게 나왔다.

예제 입력 비교는 다음 블로그의 코드를 참고하여 진행하였다.

https://hagisilecoding.tistory.com/109

백준 20055 컨베이어 벨트 위의 로봇 c++ [컴공과고씨]

위 블로그도 나와 같이 deque를 사용하지 않은 코드이기 때문에 참고할 수 있었다.

이를 통해 오류를 찾았는데, rotateRobot() 함수에서 가장 먼저 올린 로봇부터 이동하는 로직이 잘못되어 있었다.

난 그냥 R을 거꾸로 진행해주면 되겠지라는 안일한 생각으로 그냥 대충 풀었던 것 같다..

가장 먼저 올린 로봇은 내리는 위치, 즉 down의 위치와 가장 가깝기 때문에 그 위치부터 up까지 거꾸로 탐색하도록 코드를 변경해주었다.

새로 idx라는 변수를 추가하여 현재 위치가 계속 이동되도록 진행하며 로봇을 이동시켜주었다.

void rotateRobot() {
    // 가장 먼저 올린 로봇은 down 위치와 가깝기 때문에 down에서부터 up까지 차례대로 진행
    int idx = down; // 추가
    for (int i = 0; i < N; ++i) {
        int next = idx; // 변경
        idx = idx - 1 >= 0 ? idx - 1 : 2 * N - 1; // 추가
        // 현재 위치에 로봇이 있고, 다음 위치에 로봇이 없으며, 다음 위치의 내구도가 1 이상인 경우 로봇 이동
        if (R[idx] && !R[next] && A[next] >= 1) {
            R[next] = true;
            R[idx] = false;
            A[next]--;
        }
        R[down] = false; // 내리는 위치의 로봇 제거
    }
}

또 추가로 수정된 부분은 for 문의 최대 인덱스 값이다.

난 그냥 2 * N - 1부터 0까지 전부 순회를 해주었었는데, 이렇게 하면 그냥 0부터 N - 1번까지만 돌아도 된다.

어차피 down의 다음 위치들은 이미 down을 거쳐갔기 때문에 로봇이 존재하지 않을 것이다. 그리고 up에서 로봇을 새로 올리기 때문에 down 이후부터 up 사이에는 로봇이 존재하지 않을 것이다. 따라서 up과 down 사이에만 로봇의 이동을 해주면 되는 것이고, 그렇기 때문에 전체 순회를 하지 않아도 된다. 이로써 시간이 훨씬 단축되는 코드를 얻을 수 있다.

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, K, cnt = 0, up = 0, down;
vector<int> A; // 각 벨트 위치의 내구도
vector<bool> R; // 각 위치별 로봇 유무

void rotateAll() {
    // 전체 회전한다는 것은 올리는 위치와 내리는 위치가 이동한다는 것
    up = up - 1 >= 0 ? up - 1 : 2 * N - 1;
    down = down - 1 >= 0 ? down - 1 : 2 * N - 1;
    R[down] = false; // 내리는 위치의 로봇 제거
}

void rotateRobot() {
    // 가장 먼저 올린 로봇은 down 위치와 가깝기 때문에 down에서부터 up까지 차례대로 진행
    int idx = down;
    for (int i = 0; i < N; ++i) {
        int next = idx; // 다음 위치
        idx = idx - 1 >= 0 ? idx - 1 : 2 * N - 1; // 현재 위치
        // 현재 위치에 로봇이 있고, 다음 위치에 로봇이 없으며, 다음 위치의 내구도가 1 이상인 경우 로봇 이동
        if (R[idx] && !R[next] && A[next] >= 1) {
            R[next] = true;
            R[idx] = false;
            A[next]--;
        }
        R[down] = false; // 내리는 위치의 로봇 제거
    }
}

void loadRobot() {
    if (A[up] >= 1) { // 올리는 위치의 내구도가 1 이상인 경우 로봇 올림
        R[up] = true;
        A[up]--;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N >> K;
    down = N - 1; // 내리는 위치 설정
    A = vector<int>(2 * N, 0);
    R = vector<bool>(2 * N, false);
    for (int i = 0; i < 2 * N; ++i) cin >> A[i];

    // 내구도가 0인 칸의 개수가 K개보다 작을 때만 반복
    while (count(A.begin(), A.end(), 0) < K) {
        cnt++; // 단계 먼저 추가
        rotateAll(); // 벨트와 로봇 회전
        if (cnt > 1) rotateRobot(); // 로봇 회전 (첫 번째 단계에서는 로봇이 없으므로 생략)
        loadRobot(); // 로봇 올리기
    }
    cout << cnt;
    return 0;
}

 

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

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

 

오류 삽질 흔적 기록