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

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

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

 

문제 분석

삼성 스타일의 문제라고 생각했다. 뭐랄까, 문제 지문이 길고 한 번에 이해하기 쉽지 않아 처음에는 '아 되게 어렵겠다' 하고 겁먹는데, 막상 문제를 분석하면서 '어떤 알고리즘을 사용하면 될까 ?' 를 생각할 이유가 없이 그저 문제에서 시키는대로 구현만 하면 되는, 그런 스타일의 문제이다. 삼성 코딩테스트에서 주로 이런 유형이 나왔던 것 같다 (방금 블로그 작성하며 알았는데 백준 문제집 중 삼성 SW 역량 테스트 기출 문제라는 문제집이 있는데 거기에 이 문제가 포함되어 있긴 하다).

 

사실 엄청 어려운 문제는 아니지만, 문제에서 시키는대로 차근차근 잘 구현해야 한다. 출력해야 할 값은 종료될 때 단계가 몇 번째로 진행 중이었는지이다. 단계는 여러 루틴(서브 단계)으로 구성이 되는데, 종료될 때까지 이 단계를 몇 번이나 반복해 수행했느냐 라는 이야기이다. 서브 단계에 해당하는 각 루틴은 다음과 같다.

 

1. 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다.

2. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.

    2 - 1. 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.

3. 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다.

4. 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.

 

즉, 이 루틴들의 집합인 단계를 몇 번이나 반복해 수행했느냐를 구하면 되고, 별다른 알고리즘을 필요로 하지 않는다. 구현 문제이다.

 

코드

#include <iostream>
#include <vector>

using namespace std;

int n, k;
int durabilities[201];
int loadIndex, unloadIndex;
vector<int> robotPositions;
bool isLoaded[201];
int result;

void getInput();
void solve();
void printResult();

void turnAround();
void moveRobot();
void loadRobot();
void unloadRobot();
bool checkState();

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

    getInput();
    solve();
    printResult();

    return 0;
}

void getInput() {
    cin >> n >> k;
    for (int i = 1; i <= 2 * n; i++) {
        cin >> durabilities[i];
    }
}

void solve() {
    result = 0;
    loadIndex = 1;
    unloadIndex = n;

    while (true) {
        result++;

        turnAround();
        moveRobot();
        loadRobot();
        if (checkState()) {
            break;
        }
    }
}

void printResult() {
    cout << result << "\n";
}

void turnAround() {
    if (--loadIndex == 0) {
        loadIndex = 2 * n;
    }

    if (--unloadIndex == 0) {
        unloadIndex = 2 * n;
    }

    unloadRobot();
}

void moveRobot() {
    for (int i = 0; i < robotPositions.size(); i++) {
        int robotPosition = robotPositions[i];
        int nextPosition = robotPosition + 1;
        if (nextPosition > 2 * n) {
            nextPosition = 1;
        }

        if (!isLoaded[nextPosition] && durabilities[nextPosition] >= 1) {
            robotPositions[i] = nextPosition;
            isLoaded[robotPosition] = false;
            isLoaded[nextPosition] = true;
            durabilities[nextPosition]--;
        }
    }

    unloadRobot();
}

void loadRobot() {
    if (durabilities[loadIndex] != 0) {
        robotPositions.push_back(loadIndex);
        isLoaded[loadIndex] = true;
        durabilities[loadIndex]--;
    }
}

void unloadRobot() {
    if (isLoaded[unloadIndex]) {
        int offset = -1;
        for (int i = 0; i < robotPositions.size(); i++) {
            if (robotPositions[i] == unloadIndex) {
                offset = i;
                break;
            }
        }

        robotPositions.erase(robotPositions.begin() + offset);
        isLoaded[unloadIndex] = false;
    }
}

bool checkState() {
    int count = 0;
    for (int i = 1; i <= 2 * n; i++) {
        if (durabilities[i] == 0) {
            count++;
        }
    }

    return count >= k;
}

 

코드 설명

보통 나는 삼성 코딩테스트 유형 같은 문제를 풀 때는, 메서드 분리를 명확히 하는 편이다. 삼성같은 유형의 경우는 '너 이런 알고리즘 알아 ?' 하고 물어본다기보다는, '너 이런 논리적인 단계들을 코드로 풀어낼 줄 알아 ?' 를 물어보기 때문이다. 그래서 이런 논리적 단계를 코드로 변환하는 과정에서 작게 쪼개다 보면 나 스스로도 이해하기 쉽고, 또 문제를 풀다가 예상치 않은 출력이 나오면 작은 단위로 디버깅해볼 수 있기 때문에 메서드 분리를 하는 편이다.

 

이 문제 역시 마찬가지로 turnAround(), moveRobot(), loadRobot(), unloadRobot(), checkState()라는 메서드를 통해 문제를 풀었다. turnAround()는 컨베이어 벨트를 한 칸씩 돌리는 일을 담당한다. moveRobot()은 로봇을 한 칸씩 전진시키는 일을 담당하고, loadRobot()은 로봇을 컨베이어 벨트에 올리는 일을, unloadRobot()은 로봇을 컨베이어 벨트에서 내리는 일을, checkState()는 while문이 무한으로 돌지 않도록 반복문을 중단시켜주는 체크포인트 역할을 한다.