CS/Coding Test

[백준] 20055: 컨베이어 벨트 위의 로봇 python 구현

hyez 2023. 3. 30. 21:23

문제

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

컨베이어 벨트에 박스 모양 로봇을 하나씩 올리려고 한다. 로봇은 올리는 위치에만 올릴 수 있다. 언제든지 로봇이 내리는 위치에 도달하면 그 즉시 내린다. 로봇은 컨베이어 벨트 위에서 스스로 이동할 수 있다. 로봇을 올리는 위치에 올리거나 로봇이 어떤 칸으로 이동하면 그 칸의 내구도는 즉시 1만큼 감소한다.

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

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

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

 

풀이

문제를 이해하기가 너무 힘들었다.. ! 내가 문제를 풀 때 중요했던 부분들을 밑줄과, 색상으로 표시해두었다. 특히 문제에서헷갈렸던 부분은 아래와 같다.

  • 가장 처음 수행되는 단계는 1번째 단계 -> 이 말 때문에 헷갈렸는데 시작은 0 step 부터 시작임
  • 컨베이어 벨트는 한번 이동하고, 로봇은 총 두번 이동(컨베이어 벨트가 이동함과 동시에, 로봇 스스로)

풀이를 위해 로봇과, 벨트의 내구도를 관리할 두가지의 리스트를 준비한다

  1. 벨트와 그 위에 있는 로봇이 동시에 한 칸씩 이동한다.
    1. 이동했는데 내리는 위치에 도달하면 로봇은 삭제된다.
  2. 로봇이 조건에 맞춰 혼자 움직인다 
    1. 로봇 리스트의 역순으로 로봇이 존재하고, 내리는 위치가 아닐 때, 로봇이 이동한다.
    2. 다음칸에 로봇이 있거나, 다음칸의 내구도가 0이라면 로봇은 이동할 수 없다.
    3. 2-2번에 해당하지 않는다면 한 칸 이동하고, 이동한 칸의 컨베이어 벨트의 내구도는 - 1 감소한다.
    4. 만약, 이동한 곳이 내리는 위치라면 로봇은 삭제된다.
      1. 이 때, 내구도의 변화는 없다. 
  3. 2번이 끝나고 첫 번째 컨베이어 벨트의 내구도가 1 이상이라면, 새로운 로봇을 올리고 내구도는 -1 감소한다.
  4. 1-3번의 작업을 내구도가 0인 칸의 개수가 k개 이상이 될 때 까지 반복한다.

 

그 런 데

Pypy 3로 해야 돌아감.. (python 3 안돼 !)

 

CODE

import sys

n, k = map(int, input().split())
dur_list = list(map(int, sys.stdin.readline().split())) # 내구도 list
robot_list = [0] * n

step = 0

while 1:
    ### 종료 조건
    if sum(map(lambda x: x == False, dur_list)) >= k:
        break

    ### 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다.
    dur_list = [dur_list[-1]] + dur_list[:-1]
    robot_list = [robot_list[-1]] + robot_list[:-1]
    if robot_list[-1] :
        robot_list[-1] = 0

    ### 로봇이 조건에 맞춰 움직인다.
    # 가장 먼저 벨트에 올라간 로봇부터 (역순으로, 회전하기 때문에 뒤에 있는 친구가 먼저 올라간 것임), 
    for i in range(n-1, -1, -1):
        # 로봇이 있고, 맨 끝자리가 아닐 때, 
        if robot_list[i] and i != (n-1):
            # 다음 칸에 로봇이 있거나, 내구도가 1 미만이면 pass
            if robot_list[i+1] or dur_list[i+1] < 1: continue

            # 그게 아니면 움직이고, 내구도 - 1
            robot_list[i] = 0 # 떠난자리
            robot_list[i+1] = 1 # 이동한 자리
            dur_list[i+1] -= 1

            # N번째(내리는 위치)에 로봇이 도착하면 삭제함, 내구도 변화 x
            if (i+1) == (n-1):
                robot_list[i+1] = 0

    ### 로봇을 올리고 내구도 -1
    if dur_list[0] > 0:
        robot_list[0] = 1
        dur_list[0] -= 1

    step += 1

print(step)
  1.  
  1.