[삼성 SW 역량 테스트] 컨베이어 벨트 위의 로봇

  • 삼성 SW 역량 테스트 기출 문제입니다.
  • 문제해결 능력을 키우기 위해 온라인 알고리즘 문제를 풀어보고 있습니다.
  • 이곳에서 직접 문제를 풀어볼 수 있습니다.

컨베이어 벨트 위의 로봇 문제 설명

  • 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부터 2N까지의 번호가 매겨져 있다.

컨베이어 벨트 위의 로봇 문제

  • 벨트가 한 칸 회전하면 1번부터 2N-1번까지의 칸은 다음 번호의 칸이 있는 위치로 이동하고, 2N번 칸은 1번 칸의 위치로 이동한다. i번 칸의 내구도는 Ai이다. 위의 그림에서 1번 칸이 있는 위치를 “올라가는 위치”, N번 칸이 있는 위치를 **“내려가는 위치”**라고 한다.

  • 컨베이어 벨트에 박스 모양 로봇을 하나씩 올리려고 한다. 로봇은 올라가는 위치에만 땅에서 올라가고, 내려가는 위치에서만 땅으로 내려갈 수 있다. 내려가는 위치에 로봇이 있는 경우 로봇은 반드시 땅으로 내려가야 한다. 로봇이 어떤 칸에 올라가거나 이동하면 그 칸의 내구도는 즉시 1만큼 감소한다. 내구도가 0인 칸에는 로봇이 올라갈 수 없다.

  • 로봇은 컨베이어 벨트 위에서 스스로 이동할 수 있다.

  • 컨베이어 벨트를 이용해 로봇들을 건너편으로 옮기려고 한다. 로봇을 옮기는 과정에서는 아래와 같은 일이 순서대로 일어난다.

    1. 벨트가 한 칸 회전한다.
    2. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.
      1. 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.
    3. 올라가는 위치에 로봇이 없다면 로봇을 하나 올린다.
    4. 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.

  • 종료되었을 때 몇 번째 단계가 진행 중이었는지 구해보자. 가장 처음 수행되는 단계는 1번째 단계이다.

입력

  • 첫째 줄에 N, K가 주어진다. 둘째 줄에는 \(A_1, A_2, …, A_{2N}\)이 주어진다.

출력

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

제한

  • 2 ≤ N ≤ 100
  • 1 ≤ K ≤ 2N
  • 1 ≤ Ai ≤ 1,000

컨베이어 벨트 위의 로봇 문제 풀이

  • 컨베이어 벨트는 원형으로 돌아가는 벨트 시스템입니다.
  • 벨트의 움직임을 코드로 옮기기 위해서는 두 가지 방법이 있습니다.
    • 벨트의 데이터(내구성, 로봇)를 컨베이어 벨트처럼 옮기는 방법
    • 데이터를 옮기지 않고, 인덱스를 사용하여 옮기는 것 처럼 처리하는 방법
  • C++ STL에서 지원하는 컨테이너인 deque를 사용합니다. (데이터를 직접 옮기는 방법)
  • 문제를 잘 읽어보면 구현해야 할 몇 가지 함수가 눈에 들어옵니다.
    1. 벨트가 한 칸 회전하는 rotate() 함수
    2. 벨트에 존재하는 로봇을 움직이는 move() 함수
    3. 올라가는 위치에 로봇을 올리는 inRobot() 함수
    4. 내구도를 검사하는 checkDurability() 함수
  • 벨트를 구성하는 자료구조를 먼저 설계합니다.
    • 벨트의 내구성
    • 로봇의 존재 여부
1
2
3
4
5
6
7
8
9

typedef struct BELTS_T
{
    int durability;
    bool isRobot;
} BELTS;

// 전역 변수
std::deque<BELTS> belts;
int N, K;
  • 각 함수를 구현합니다.

컨베이어 벨트 위의 로봇: 벨트 회전 함수

  • deque는 push와 pop을 front와 back에서 사용할 수 있습니다.
  • 2N 위치에 있는 벨트는 이동 시 1번 칸으로 움직이므로 마지막 데이터를 떼어내고 앞으로 붙입니다.
1
2
3
4
5
6
7
8
9

// 벨트 회전
void rotate()
{
    belts.push_front(belts.back());
    belts.pop_back();

    // 로봇 내리기
    belts[N - 1].isRobot = false;
}

컨베이어 벨트 위의 로봇: 로봇 이동 함수

  • 벨트가 회전하고 나서 로봇이 움직입니다.
  • 로봇이 내리는 위치는 N 입니다.
    • 컨베이어 벨트가 윗 줄과 아랫 줄로 구성되어 2N으로 표현했음을 기억해야 합니다.
  • 내리는 위치에서 가장 가까운 로봇부터 움직여야 하므로 N - 2에서 첫 번째 위치까지 로봇을 조사합니다.
    • 문제에서 첫 번째 위치를 1로 표현했음을 기억해야 합니다. (코드에서는 0으로 사용)
    • 내리는 위치(N) 또는 그 뒤에 있는 벨트(N + 1 ~ 2N)는 로봇이 존재하지 않습니다. (내리는 위치에서 모두 내리기 때문)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

// 로봇이 이동한다.
void move()
{
    for (int i = N - 2; i >= 0; i--)
    {
        // 만약 로봇이 있으면..
        if (belts[i].isRobot == true && 
            belts[i + 1].isRobot == false &&
            belts[i + 1].durability > 0)
        {
            belts[i].isRobot = false;
            belts[i + 1].isRobot = true;
            belts[i + 1].durability--;
        }

        // 로봇 내리기
        belts[N - 1].isRobot = false;
    }
}

컨베이어 벨트 위의 로봇: 로봇 올리기 함수

  • 로봇이 올라갈 수 있는 조건은 다음과 같습니다.
    • 해당 벨트에 로봇이 존재하지 않는 경우
    • 해당 벨트의 내구성이 0보다 큰 경우
  • 로봇이 올라갈 수 있는 위치는 첫 번째 위치이므로 인덱스 0을 사용합니다.
1
2
3
4
5
6
7
8
9

// 로봇 올리기
void inRobot()
{
    if (belts[0].isRobot == false && belts[0].durability > 0)
    {
        belts[0].isRobot = true;
        belts[0].durability--;
    }
}

컨베이어 벨트 위의 로봇: 내구성 검사 함수

  • 모든 벨트를 검사하여 내구성이 0인 갯수를 구합니다.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// 내구성 검사
int checkDurability()
{
    int zero = 0;
    for (const auto& belt : belts)
    {
        if (belt.durability == 0)
            zero++;
    }

    return zero;
}

컨베이어 벨트 위의 로봇: 실행 코드

  • 데이터를 입력받아 단계를 출력하는 메인 함수를 작성합니다.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

int main()
{
    // 데이터 입력
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    std::cin >> N >> K;
    for (int i = 0; i < 2 * N; i++)
    {
        int dura;
        std::cin >> dura;
        BELTS belt;
        belt.durability = dura;
        belt.isRobot = false;

        belts.push_back(belt);
    }

    int step = 1;
    bool isRun = true;
    while (isRun)
    {
        // 벨트 회전
        rotate();

        // 로봇 이동
        move();

        // 로봇 올리기
        inRobot();

        // 종료 조건 검사
        int zero = checkDurability();
        if (zero >= K)
            break;

        step++;
    }

    printf("%d", step);

    return 0;
}