알고리즘

[백준] 20055 컨베이어 벨트 위의 로봇 - 골드 5

swanzzz 2025. 6. 22. 22:07
반응형

[오늘의 문제]

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

[오늘의 학습 키워드]

  • 구현
  • 자료구조
  • 시뮬레이션

1. 문제설명

 

컨베이어 벨트가 순서대로 동작합니다.

 

벨트에 로봇이 올라가면 내구도가 1 감소하고, 로봇이 다음번 벨트로 이동할때에도 내구도가 1 감소합니다.

 

벨트에 로봇을 올리고, 로봇이 이동하고, 벨트가 회전할때 모든 동작이 완료된 후 내구도가 K개 이상인 벨트가 있는 경우 종료하고 그때의 단계를 출력하는 문제 입니다.

[제한사항]

  • 시간 제한 1초
  • 메모리 제한 512MB
  • 2 ≤ N ≤ 100
  • 1 ≤ K ≤ 2N
  • 1 ≤ Ai ≤ 1,000

2. 접근방식

문제의 요구사항을 그대로 구현만 하면 되는 쉬운 문제 입니다.

 

요구사항을 분석하면

 

컨베이어 벨트에 로봇을 올리는 위치는 항상 0번 이고 로봇이 내려가는 위치는 항상 N번 입니다.

로봇은 컨베이어 벨트 위에서 N번칸에 도착하면 언제든지 내려갈 수 있습니다.

또한 로봇은 벨트위에서 스스로 이동할 수 있습니다.

 

모든 컨베이어 벨트의 동작은 다음의 순서를 따릅니다.

 

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

여기서 로봇이 내려가는 조건은 2가지 존재하죠

 

1.번 벨트가 회전해서 로봇이 N번칸에 도착하는 경우

2. 로봇이 이동해서 N번 칸에 도착하는 경우

 

이 경우에 로봇을 내려주면 되고 나머지는 그대로 구현만 하면 됩니다.

3. 코드

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

'''

import sys
input = sys.stdin.readline
from collections import deque

N, K = map(int, input().split())
belt = deque(list(map(int, input().split())))
robot = deque([False] * N)

answer = 0

while True:
    answer += 1

    # 1. 벨트 회전
    belt.rotate(1)
    robot.rotate(1)

    # 로봇 내리기
    robot[N - 1] = False

    # 2. 벨트에 올라간 순서대로 로봇 이동
    for i in range(N - 2, -1, -1):
        if robot[i] and belt[i + 1] > 0 and not robot[i + 1]:
            robot[i] = False
            robot[i + 1] = True
            belt[i + 1] -= 1

    # 로봇 내리기
    robot[N - 1] = False

    # 3. 로봇 올리기
    if belt[0] > 0:
        belt[0] -= 1
        robot[0] = True

    # 4. 내구도 0인 칸의 갯수 세주기
    if belt.count(0) >= K:
        break

print(answer)

[코드설명]

import sys
input = sys.stdin.readline
from collections import deque

N, K = map(int, input().split())
belt = deque(list(map(int, input().split())))
robot = deque([False] * N)

 

입력을 받아줍니다.

 

벨트가 회전하기 때문에 queue 자료구조를 이용해 주면 편하게 구현이 가능합니다.

따라서 입력받을때 deque 형식으로 입력받고, 로봇의 위치를 표시할 robot 배열역시 벨트와 동일하게 동작해야 하니 deque 형식으로 만들어 주었습니다.

answer = 0

while True:
    answer += 1

    # 1. 벨트 회전
    belt.rotate(1)
    robot.rotate(1)

    # 로봇 내리기
    robot[N - 1] = False

    # 2. 벨트에 올라간 순서대로 로봇 이동
    for i in range(N - 2, -1, -1):
        if robot[i] and belt[i + 1] > 0 and not robot[i + 1]:
            robot[i] = False
            robot[i + 1] = True
            belt[i + 1] -= 1

    # 로봇 내리기
    robot[N - 1] = False

    # 3. 로봇 올리기
    if belt[0] > 0:
        belt[0] -= 1
        robot[0] = True

    # 4. 내구도 0인 칸의 갯수 세주기
    if belt.count(0) >= K:
        break

print(answer)

 

문제에서 요구하는 것은 종료되었을 때 몇 번째 단계가 실행중인지를 구하는 것입니다.

단계는 시작이 1단계로 시작하기 때문에 while 문을 시작하자 마자 answer 부터 늘려주었습니다.

 

이제 문제의 요구사항을 순서대로 구현해 주었습니다.

 

1. 벨트의 회전

벨트의 회전의 경우 popleft 와 append로 구현할 수 있는데 더 간단히 rotate가 가능합니다.

rotate(1)은 1번 회전한다는 의미입니다.

 

벨트가 회전하면 로봇이 내려오는 경우가 있으니 로봇을 일단 내려줍니다.

해당 위치에는 로봇의 존재여부와 상관없이 무조건 False가 되어야 하기 때문에 바로 False를 입력해 주었습니다.

 

2. 로봇의 이동

로봇의 이동은 먼저 벨트에 올라간 순서대로 접근해 주어야 합니다.

따라서 인덱스를 역순부터 접근하여 로봇이 있고, 다음칸에 로봇이 없고, 다음칸의 내구도가 1이상인 경우 로봇을 이동해 주었습니다.

 

로봇이 이동하면 해당칸의 내구도는 즉시 1 감소하고 로봇의 위치가 변경되죠

이때 역시 로봇이 이동하며 N번칸에 도착할 수 있으니 2번 동작이 완료되면 바로 로봇을 내려줍니다.

 

3. 로봇 올리기

로봇을 올릴때는 해당 위치의 내구도가 1이상 있어야 올릴 수 있습니다.

로봇이 처음칸인 0번칸에 올라간다면 그 즉시 내구도가 1 감소합니다.

 

4. 내구도가 0인 칸의 갯수 세어주기

앞서 위 과정들은 순서대로 발생하며 내구도가 0인 칸은 해당 동작들이 종료된 후 세어주어도 answer에는 변화가 없습니다.

따라서 앞선 모든 과정이 순서대로 종료되었을 때 내구도가 0인 칸을 세어주었습니다.

 

이때 내구도가 0인 칸이 K개 이상이라면 종료해주었습니다.

4. 결과

[회고]

생각보다 문제가 훨씬 쉬웠습니다. 

queue 자료구조만 이용할 줄 안다면 바로 해결이 가능했기에 표시 난이도는 골드 5지만 체감 난이도는 실버 3 정도 였습니다.

 

또한 최초 문제의 설명만 보면 길이가 N인 컨베이어 벨트에 길이가 2N인 벨트가 위아래를 감싸며 올라가 있다고 했습니다.

문제의 조건을 그대로 구현하면 해당 사항을 그대로 구현해야 하기에 귀찮지만 결국에는 컨베이어 벨트의 아래쪽에 해당하는 부분들은 사용되지 않는 부분이고 괜히 길이만 늘어나기에 문제 해결속도만 늦어지는 부분입니다.

 

따라서 문제에서 필요하지 않은 아래쪽 벨트는 구현하지 않고 실제 동작이 발생하는 위쪽의 벨트만 구현하더라도 쉽게 해결이 가능한 문제 였습니다.

 

다음에도 비슷한 문제를 풀면서 학습을 이어 나가겠습니다.

반응형